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

🧨 백준 2178번 미로탐색

문제 난이도 : 실버1

문제 링크 : www.acmicpc.net/problem/2178

2178번: 미로 탐색

🧨 알고리즘 선택 및 C++ 코드

처음 문제를 봤을 땐 좀 낯설었다. 뭔가 너비우선탐색을 사용하는 거 같은데 어떻게 사용할지 한참 고민했다. 미로에서 칸 이동을 해야 하므로 어쩔 수 없이 상하좌우 대소비교가 들어가야했다. 그래프 탐색을 이용한 문제는 대부분 원하는 값만을 구하려고 하면 어렵게 느껴진다. 갈 수 있는 모든 칸에 대해 지나야 하는 최소 칸 수를 계산해야 (N, M)까지 가는 최소 경로를 구할 수 있다. 똑같이 BFS를 사용하되, 처음에 2차원 형태의 미로 모양으로 입력받기 때문에 이를 좌표로 바꿔줘야 한다. 따라서 pair<int, int> 로 (x, y) 좌표를 표현했다.

예전에 어디선가 상하좌우를 나타내는 표현으로 dx[] = { -1, 1, 0, 0 }, dy[] = { 0, 0, -1, 1 } 을 본 적이 있다. 다시 찾아서 적용해보니 코드가 이렇게 깔끔해질 수가 없다! 상하좌우 4 방향으로 한 칸 이동했을 때 그 칸이 유효한 칸인지를 체크하고, 유효하며 내가 갈 수 있는(=1일때) 길이라면 다음에 가볼 수 있도록 큐에 추가한다. 이렇게 모든 칸에 대해 상하좌우를 고려해 이동하므로 BFS(너비우선탐색)를 이용했다. 

#include <iostream>
#include <queue>

using namespace std;

int N, M;
int dx[] = {-1, 1, 0, 0}; // 좌, 우, 상, 하
int dy[] = {0, 0, -1, 1};

void BFS(int G[101][101]) {
    // start : maze[0][0]
    // end   : maze[N-1][M-1]
    int isMarked[101 * 101] = {false};
    int isinQueue[101 * 101] = {false};
    
    queue<pair<int, int>> q;
    q.push(make_pair(0, 0));
    
    while(!q.empty()) {
        int cur_x = q.front().first;
        int cur_y = q.front().second;
        q.pop();
        
        for(int i = 0; i < 4; i++) {
            int nx = cur_x + dx[i];
            int ny = cur_y + dy[i];
            
            if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
            if(G[nx][ny] == 0) continue;
            if(G[nx][ny] == 1) {
                G[nx][ny] = G[cur_x][cur_y] + 1;
                q.push(make_pair(nx, ny));
            }
        }
    }
    // 내가 시도했던 길 출력
    // for(int i = 0; i < N; i++) {
    //     for(int j = 0; j < M; j++) {
    //         cout << G[i][j] << ' ';
    //     }
    //     cout << '\n';
    // }
    cout << G[N - 1][M - 1];
}

int main()
{
    cin >> N >> M;
    int maze[101][101] = {0};
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            scanf("%1d", &maze[i][j]);
        }
    }
    
    BFS(maze);

    return 0;
}

 

그래프 알고리즘은 문제를 많이 풀어봐야 감이 올 거 같다