[BOJ 2178 C++] 미로탐색

2178번: 미로 탐색

문제 분석 및 풀이 방식

• 1로 표현된 부분으로 이동하며 최단거리를 구한다.
• 최단거리 : BFS를 이용한다.
• 2차원으로 표현되어 있으므로 x,y 좌표를 활용한다.
• 각 좌표마다 몇 칸을 이동해서 온건지 저장해주는 이차원 배열도 만든다.
• x, y 좌표를 움직일때, 4칸짜리 배열을 두개 선언하여 x, y좌표를 상하좌우 움직일 수 있다.

int n, m;
int maze[101][101];// 미로 표현용 2차원 배열
bool visited[101][101];// 좌표에 방문 했는지에 대한 2차원 배열
int xDir[4] = {0, 1, 0, -1};//x좌표 방향 설정을 위한 배열
int yDir[4] = {1, 0, -1, 0};//y좌표 방향 설정을 위한 배열
int cnt[101][101];//각 좌표마다 몇칸을 이동해서 온건지 저장하는 2차원 배열

void bfs() {
    queue<pair<int, int>> q;// x,y 좌표를 저장하는 큐
    visited[0][0] = true;//(0,0)부터 시작
    q.push({0, 0});
    cnt[0][0] = 1;
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nextX = x + xDir[i];
            int nextY = y + yDir[i];
            //다음 좌표의 후보는 현재의 상하좌우
            if (visited[nextX][nextY] || maze[nextX][nextY] == 0) continue;
            //다음 좌표 후보에 방문한적 있거나 통로가 아니면 다음 후보로 진행
            if (0 <= nextX && nextX < m && 0 <= nextY && nextY < n) {
            //다음 좌표의 위치는 (0<=x<m) & (0<=y<n)
                visited[nextX][nextY] = true;
                q.push({nextX, nextY});
                cnt[nextX][nextY] = cnt[x][y] + 1;
            }
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        string str;
        cin >> str;
        for (int j = 0; j < m; j++) {
            maze[j][i] = str[j] - '0';
        }
    }
    bfs();
    cout << cnt[m - 1][n - 1];//(m-1,n-1)좌표에 몇번 이동하여 왔는지 출력
}

배운 점

• x, y 좌표를 다루는 문제 자체가 어색했고, 배열을 두개 만들어 푸는 방법을 써본게 처음이라 어색했다.
  하지만 꼭 알아둬야할 풀이 방법이란 생각이 들었고 충분히 익혀야 겠다는 생각이 들었다.