백준 / 2178 / 미로 탐색 / C++ / 알고리즘 문제풀이 / BFS

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

2178번: 미로 탐색

큐에 좌표값을 저장해서 이동할 수 있는 곳이면 거리값들을 1씩 증가시키면서 마지막에 거리 정보를 저장한 배열의 [N][M]값을 출력하는 BFS탐색으로 문제를 해결해보았습니다.

 

그런데 첫번째 코드에서 메모리초과가 발생했습니다. 

메모리제한이 192MB인데 , 배열의 크기도 크지않은데 어째서 메모리초과가 나는 것인지 ..궁금해 하다가 구글링 해본 결과 BFS를 사용할 때, 종종 발생하는 일이더라구요. 예를 들면 아직 (3,3)의 좌표는 방문하지 않은상태인데 갈 수 있는 곳으로의 조건이 판별되어 인접 좌표에서 중복으로 큐에 데이터를 push하게 되어서 (3,3)이라는 데이터가 큐에 여러개가 들어가있어 메모리 초과를 초래한다는 글을 확인했습니다. (siezeof()로 확인해보니 pair<int,int>라고 해봤자 하나에 8Byte수준인데 이것 때문에 메모리초과가 난다는 사실을 완벽히 이해하지는 못했습니다 .. ㅜㅜ VS에서 실시간으로 메모리 확인해보면서 체크해보려했는데 실패했습니다.) 그래서 미리 BFS함수 들어가기 전 (1,1)의 좌표를 방문처리하고 BFS안에서 조건을 만족하는 좌표는 바로 방문처리를 함으로써 중복되는 좌표가 큐에 들어가는 것을 방지하도록 코드를 수정했더니 문제 없이 정답처리가 되었습니다 !

 

 

 

#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
queue<pair<int, int>> Q;
int N, M;
char map[101][101];
int dist[101][101] = {0};
int dx[4] = { 0,0,-1,1 };
int dy[4] = { 1,-1,0,0 };
bool visited[101][101] = {false};
 
 
void BFS()
{
    Q.push(make_pair(1, 1));
 
    while (!Q.empty())
    {
        auto cur = Q.front();
        Q.pop();
        int x = cur.first;
        int y = cur.second;
       //메모리 초과 당시 코드 -> 26번째 줄에서 visited[newX][newY] = true;
        
 
        for (int i = 0; i < 4; i++)
        {
            int newX = x + dx[i];
            int newY = y + dy[i];
 
            if (map[newX][newY] == '1' && newX >= 1 && newY >= 1 && newX <= N && newY <= M && visited[newX][newY] == false)
            {
                
                Q.push(make_pair(newX, newY));
                visited[newX][newY] = true; // 38번째 줄이 위에 26번째 줄에 존재했었음
                dist[newX][newY] = dist[x][y] + 1;
            }
        }
 
    }
 
}
 
 
 
int main()
{
    cin >> N >> M;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            cin >> map[i][j];
        }
    }
 
    dist[1][1] = 1;
    visited[1][1] = true;  //메모리 초과 당시 코드에선 61번째 줄이 BFS안에서 해결되므로 없었음 !
    BFS();
 
    cout << dist[N][M] << endl;
 
}
 
 

 

* 스스로 생각해보고 구글링하며 작성한 내용이기 때문에 틀린 부분이 있을수 있습니다 ! 

댓글로 수정해주시면 감사하겠습니다. (코드는 사이트에서 정상 채점처리 O)