[백준 2178번] 미로 탐색

---

문제 화면

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

문제 풀이

이 문제는 queue 자료구조를 이용하는 BFS의 대표적인 문제이다. 2178 그림 문제와 다른점은 vis 배열에 단순히 방문했다는 표시로 1을 넣는 것이 아닌 시작점부터 거리를 넣어주는 부분이다. 문제에서 요구하는 것이 좌측 상단에서 우측 하단으로 가는 최소거리를 물어보기 때문에 모든 연산을 마치고 나서 가장 우측 하단의 vis 배열 값을 출력해주면 된다.

제출 코드

#include <iostream>
#include <queue>

using namespace std;

int map[102][102];
int vis[102][102];
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m, dis = 0;
    string s;
    cin >> n >> m;
    for(int i = 0 ; i < n ; i++) {
        cin >> s;
        for(int j = 0 ; j < m ; j++) {
            int temp = s[j] - '0';
            map[i][j] = temp;
        }
    }

    for(int i = 0 ; i < n ; i++) {
        for(int j = 0 ; j < m ; j++) {
            if(map[i][j]!=1 || vis[i][j]!=0) continue; // 땅이 아니거나 이미 방문한 경우

            vis[i][j] = 1; // 땅이고 방문하지 않은 경우 방문 찍어라
            queue<pair<int,int>> q;
            q.push({i, j});

            while(!q.empty()) {
                auto cur = q.front(); q.pop(); // pair<int,int> cur -> auto cur
                int dis = (vis[cur.first][cur.second]) + 1;
                for(int dir = 0 ; dir < 4 ; dir++) {
                    int nx = cur.first + dx[dir];
                    int ny = cur.second + dy[dir];
                    if(nx<0 || nx>=n || ny<0 || ny>=m) continue; // 지도 범위 밖
                    if(map[nx][ny]!=1 || vis[nx][ny]!=0) continue; // 땅이 아니거나 이미 방문한 경우
                    q.push({nx, ny});
                    vis[nx][ny] = dis;                    
                }
                
            }
        }
    } 

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

    return 0;
}

결론

BFS는 마스터한다고 생각하고 무조건 많이 풀어봐야 할 것 같다. 저번 문제랑 거의 차이가 없는데 이번에도 인덱스 문제로 삽질했다. 꼼꼼하게 보자.

출처

• https://blog.encrypted.gg/941?category=773649