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

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

2178번: 미로 탐색

 

 

어떤 문제인가?

n*m 크기의 공간에서 0과 1로 미로를 만든다. 1은 지나갈 수 있고 0은 지나갈 수 없는 곳이다.

이때 왼쪽 위부터 출발해 오른쪽 아래까지 갈 수 있는 최소 거리를 구하면 된다.

 

 

 

 

접근 방법 

이동의 가중치가 없는 그래프에서 최단 경로를 구하는 것이기 때문에 bfs를 통해 접근하였다. 

 

int miro[101][101];
bool visited[101][101];

먼저 미로를 저장할 이차원 배열과 방문처리를 해줄 이차원 배열을 선언해준다.

 

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

위 두 배열은 미로에서 한 좌표가 주어졌을 때 상, 하, 좌, 우로 이동하기 위한 배열이다.

 

 

int n, m;
cin >> n >> m;

 문제에서 주어진 n과 m을 입력받는다.

 

for (int i = 0; i < n; i++) {
    string s;
    cin >> s;

    for (int j = 0; j < m; j++) {
        miro[i][j] = s[j] - '0';
    }
}

수들이 붙어서 입력되기에 string으로 입력받아서, 각 인덱스들을 정수 형태로 미로에 넣어준다.

 

bfs(0, 0);

이제 (0, 0)부터 그래프 탐색을 시작할 것이다.

 

 

void bfs(int x, int y) {
    queue<pair<int, int>> q;
    q.push({x, y});

    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        for (int i = 0; i < 4; i++) {
            int x2 = x + dx[i];
            int y2 = y + dy[i];

            if (miro[x2][y2] == 0) {
                continue;
            }
            if (x2 < 0 || x2 >= n || y2 < 0 || y2 >= m) {
                continue;
            }

            if (!visited[x2][y2]) {
                visited[x2][y2] = true;
                miro[x2][y2] = miro[x][y] + 1;
                q.push({x2, y2});
            }
        }
    }
}

 

탐색에 필요한 큐를 선언해준다. 이때 x좌표와 y좌표를 저장해야 하니 pair를 사용해준다.

큐에 넘겨받은 x좌표 y좌표를 추가해준다.

그리고 큐가 빌 때까지 반복문을 통해 탐색해나간다.

큐의 맨 앞 first에 저장된 x좌표와 second에 저장된 y좌표를 꺼내온다.

그리고 큐를 팝 해준다.

 

이제 위에서 선언했던 이동 배열을 통해 좌표를 움직일 것이다.

상, 하, 좌, 우로 이동시킨 새로운 x좌표와 y좌표가 생긴다.

그때의 위치가 저장하는 값이 0이라면 이동할 수 없는 곳이므로 continue를 통해 다음 반복으로 넘어간다.

또, 좌표가 n*m 좌표의 범위를 벗어났다면 이동할 수 없는 곳이므로 continue를 통해 다음 반복으로 넘어간다.

 

이 두 예외처리를 통과했다면, 이제 이 좌표가 이동할 수 있는 곳이라는 것이다.

하지만 방문 여부를 확인해야 한다.

이제 만약 새로운 좌표가 방문되지 않았다면 방문처리를 해준다.

또 새로운 좌표에 저장된 값에 +1을 해준다. 이 뜻은 이전 좌표에서 새로운 좌표까지 가는 거리가 1이기 때문이다.

그리고 큐에 새로운 좌표들을 추가해준다.

 

여기서 잠깐,

miro [ x ][ y ] = 10의 뜻은 (x, y)까지 이동하는데 10칸을 지나야 한다는 것이다.

 

 

이렇게 탐색을 하다 보면 결국 이차원 배열 [ n - 1][ m - 1] 번째 인덱스에 (n, m)까지 이동하는데 지나야 하는 칸수가 저장되어 있을 것이다.

 

cout << miro[n - 1][m - 1];

따라서 [ n - 1][ m - 1] 번째 인덱스 값을 출력해주면 된다.

 

 

무엇이 어려웠는가?

이 문제는 이동에 필요한 배열 dx, dy만 사용할 줄 안다면 크게 어렵지 않은 문제인 것 같다.

0인 곳과 n*m의 범위를 벗어나는 곳만 예외처리를 해주면 되어서 간단했다.

 

처음엔 거리를 저장할 배열을 따로 하나 만들까 했지만,

마침 딱 예쁘게 1로 입력을 받아서 이동해야 하는 칸수를 1씩 쌓아가면 굳이 새로운 배열을 만들 필요가 없다고 생각했다.