[BAE/<JOON> 문제풀이] 2178. 미로

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

2178번: 미로 탐색

말 그대로 미로를 탐색해서 1,1 부터 n, m까지 최단 경로를 찾아내는 문제다.

 

어제 풀던 섬을 오늘도 못풀어서 1일 1문제는 해야하기 때문에 다른 문제로 때운다.. (ㅠㅠ)..

 

이 문제도 bfs로 굉장히 단순한데, 내가 그 동안 bfs문제들을 모조리 잘못 풀이하고 있었다는 것을 알았다. 

 

우선 아래 코드를 보자.

 

    queue<coor> q;
    q.push({ 1, 1, 1 });
    while (!q.empty()) {
        int x = q.front().x;
        int y = q.front().y;
        int c = q.front().c;        
        arr[x][y] = 0;
        q.pop();
        for (int i = 1; i <= 4; i++) {
            int mx = x + mvx[i];
            int my = y + mvy[i];
            if (mx > n || mx < 1 || my > m || my < 1 || arr[mx][my] != 1) continue;
            if (mx == n && my == m) {
                cout << c + 1 << endl;
                return 0;
            }
                        
            q.push({ mx, my, c + 1 });
        }
    }

평소에 항상 작성하는 큐를 이용한 탐색 코드다.

 

보면 큐에서 노드 하나를 꺼낸 후에 방문했다는 표시를 남기고 있다.

 

arr[x][y] = 0; 

 

이런 식으로 노드를 꺼낸 후에 방문 표시를 한다면 데이터가 조금만 커져도 메모리 초과가 발생한다.

 

만약 탐색을 하는 과정에서 a라는 노드를 탐색하고 큐에 집어넣었다고 가정해보자.

 

위 문제는 최단거리를 탐색하는 문제이므로 a 노드가 발견된 시점에서 a노드로 갈 수 있는 최단 경로는 결정된 것이나 다름없다. 

 

즉, 다른 최단 경로를 찾을 필요도 없고 a노드는 다른 탐색 루트에서 발견되어야할 이유가 없다.

 

하지만 위 코드처럼 a가 큐에서 꺼내진 다음에 방문표시가 된다면 a가 큐에 들어간 다음 다른 큐들을 탐색하는동안 a노드가 또 발견된다면 방문 표시가 안된 상태이기 때문에 a는 또 큐에 들어가게 될 것이다.

 

즉, 같은 탐색을 수없이 반복하는 것이다. 이러한 이유로 위 문제에 이 스니펫을 사용할 경우, n, m의 최댓값이 100밖에 되지 않음에도 불구하고 메모리 초과 에러가 발생하게 된다.

 

매일 사용하는 코드라서 별 생각 없었는데 이런 실수를 하고있는지 몰랐다..

 

그래서 섬 문제에도 같은 문제가 있어 수정하고 맞출 줄 알았는데, 틀렸다. 또 다른 문제가 있나보다...

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

vector<vector<int> > arr;

int mvx[5] = { 0, 1, 0, -1, 0 };
int mvy[5] = { 0, 0, 1, 0, -1 };

struct coor {
    int x, y, c;    
};

int main()
{
    int n, m;
    cin >> n >> m;
    arr.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        arr[i].resize(m + 1);
        for (int j = 1; j <= m; j++) {
            char imsi;
            cin >> imsi;
            arr[i][j] = imsi - 48;
        }
    }

    queue<coor> q;
    q.push({ 1, 1, 1 });
    while (!q.empty()) {
        int x = q.front().x;
        int y = q.front().y;
        int c = q.front().c;        
        q.pop();
        for (int i = 1; i <= 4; i++) {
            int mx = x + mvx[i];
            int my = y + mvy[i];
            if (mx > n || mx < 1 || my > m || my < 1 || arr[mx][my] != 1) continue;
            if (mx == n && my == m) {
                cout << c + 1 << endl;
                return 0;
            }
            arr[mx][my] = 0;
            /*
            큐에 집어 넣을 때 마킹해야함
            빼낼때 마킹을 하게되면 빼기 전까지는 미방문 정점이기 때문에 같은 노드가 여러개 큐에 들어가서 메모리 초과가 발생함
            */
            q.push({ mx, my, c + 1 });
        }
    }

    cout << -1 << endl;
    return 0;
}