[Baekjoon(백준)][2178번] 미로 탐색(C++)

안녕하세요! 오늘은 코딩테스트 문제 중 하나인 "미로 탐색" 문제를 해결하는 방법에 대해 설명하려고 합니다. 이 문제에서는 N×M 크기의 미로 내에서 시작 위치 (1, 1)에서 출발하여 목적지 (N, M)까지 이동할 때 지나야 하는 최소 칸 수를 찾는 문제입니다.문제를 해결하는 과정과 코드를 자세히 알아보겠습니다.

문제링크:

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

문제 개요

"미로 탐색" 문제는 N×M 크기의 미로 내에서 시작 위치 (1, 1)에서 출발하여 목적지 (N, M)까지 이동할 때 지나야 하는 최소 칸 수를 찾는 문제입니다. 미로 내에서 이동할 수 있는 칸은 '1'로 표시되며, 이동할 수 없는 칸은 '0'으로 표시됩니다.

해결 방법

이 문제는 너비 우선 탐색(BFS) 알고리즘을 사용하여 해결할 수 있습니다. BFS를 사용하면 시작 위치에서부터 거리에 따라 탐색을 확장해 나가므로, 목적지에 도달했을 때의 거리가 바로 최소 칸 수가 됩니다.

코드 구현

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// 미로의 크기와 방문 여부, 미로 정보를 저장할 변수 선언
int n, m = 0;
bool visited[105][105];
int a[105][105] = {};

// 네 방향 이동을 위한 배열
int dy[] = { -1,0,1,0 };
int dx[] = { 0,1,0,-1 };

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    // 미로 정보 입력 받기
    scanf_s("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf_s("%1d", &a[i][j]);
        }
    }

    // BFS를 위한 큐
    queue<pair<int,int>> q;
    q.push({0,0}); // 시작 위치 큐에 추가
    visited[0][0] = true; // 시작 위치 방문 표시

    while (!q.empty())
    {
        pair<int, int> current = q.front(); // 현재 위치
        q.pop();
        for (int k = 0; k < 4; k++) { // 네 방향 탐색
            int ny = current.first + dy[k];
            int nx = current.second + dx[k];
            // 미로 범위를 벗어나거나, 이동할 수 없는 칸, 이미 방문한 칸은 무시
            if (ny < 0 || ny >= n || nx < 0 || nx >= m || a[ny][nx] == 0 || visited[ny][nx]) continue;
            
            // 다음 칸으로 이동할 때 거리 1 증가
            a[ny][nx] = a[current.first][current.second] + 1;
            visited[ny][nx] = true; // 방문 표시
            q.push({ny,nx}); // 다음 위치 큐에 추가
        }
    }
    cout << a[n-1][m-1] << "\n"; // 목적지까지의 최소 거리 출력
}

코드 설명

이 코드는 BFS 알고리즘을 사용하여 미로의 각 칸을 최단 거리로 탐색합니다. 큐에는 탐색할 위치가 저장되며, 각 위치에 도달할 때마다 그 위치까지의 거리를 갱신합니다. 최종적으로 목적지 칸에 저장된 값이 시작 위치에서 목적지까지의 최소 거리가 됩니다.

결론

"미로 탐색" 문제는 BFS 알고리즘을 활용하여 각 칸까지의 최소 거리를 계산함으로써 해결할 수 있는 대표적인 그래프 탐색 문제입니다. BFS를 이해하고 올바르게 적용하는 것이 중요합니다.