[BFS/중] 2178번 미로 탐색

기본 BFS문제에서 약간 생각을 좀 더 해야되서 난이도를 중으로 채택했다.

해설

4 6

110110

110110

111111

111101

이런 미로가 있다고 치자. 

기본 bfs의 동작 방식은 큐에 다음 방문해야할 곳을 저장해 놓고 큐에서 하나하나 꺼내면서 그 위치에 방문해가면서 방문했을때 문제 조건에 맞는 어떤 처리를 해준다. 이 행동을 큐가 완전히 빌때까지 무한 반복 하는것이다.

하지만 여기서는 bfs를 해 나가면서 현재 내가 방문한 곳이 시작점으로부터 얼마나 떨어져있는지를 기록해 놓아야 한다. 그러기 위해서 나는 2차원 memo라는 배열을 하나 더 선언했고, 이곳에 현재 방문한 곳부터 시작점까지의 거리를 기록해나갔다.

while(xdeq.size() != 0)

    {

        

        int x = xdeq.front();

        int y = ydeq.front();

        int mark = length.front(); //현재 위치에 표시해야할 숫자

        xdeq.pop_front();ydeq.pop_front();length.pop_front(); //위치 방문

        

        memo[x][y] = mark++; // 위치를 방문해서 현재 땅에 시작점으로부터의 거리 표시

        for(int i=0; i<4; i++) //그다음 방문해야될 위치를 큐에 넣는다.

        {

            int nextX = x + diffx[i];

            int nextY = y + diffy[i];

            

            if(nextX >=1 && nextX <=n && nextY >=1 && nextY <=m && input[nextX][nextY] == 1)

            {

                xdeq.push_back(nextX);

                ydeq.push_back(nextY);

                length.push_back(mark);

                input[nextX][nextY] = 0;    //다음 방문할 위치를 넣으면서 동시에 그 위치는 방문했다고 표시함. 그래야 중복 방문을 막을 수 있다.

            }

        }

    }

위의 코드가 bfs 핵심 코드이다.

현재 위치를 방문해서 현재 땅에서 시작점까지의 거리를 memo라는 2차원 배열에 표시해 주고, 그 다음에 방문해야 할 곳을 큐에 넣는것과 동시에

다음 방문해야 하는 땅에 표시해야 할 숫자 까지 큐에 넣었다.

예를 들어 시작 포인트 (1,1)에서는 땅에 1이 표시 돼야 하며 그다음 위치 (2,1) (1,2)에는 땅에 표시해야할 숫자가 2이다. 

그렇게 하기 위해서는

(2,1)을 큐에 넣고 (1,2)을 큐에 넣고 숫자 2도 2번 큐에 넣어야 한다.

그리고 나서 중요한게 다음 방문해야할 위치를 큐에 넣음과 동시에 그곳을 0으로 만듦으로써 중복 방문을 막아야 한다 .처음에 이것을 신경쓰지 못해서 메모리 초과 오류가 떴었다.

무슨 소리냐면

           A         B

    E    D     F   G    H               

이런 식으로 있을때 bfs를 하게 되면 

A는 자식으로 E D F 를 차례대로 넣고 B도 마찬가지로 F G H를 넣을 것이다. 하지만 F는 A가 방문을 하게 될 예정이 므로 굳이 B가 다시 F를 방문하지 않아도 된다.

A가 E D F 라는 자식을 큐에 넣을때 E D F에 방문했다고 표시하게 되면 B가 다음 방문해야할 곳을 큐에 넣으려고 할때 F는 이미 방문했다고 표시 되있으므로 G와 H만 자식에 넣게 된다.

즉 중복 방문을 막은것이다. 이렇게 되면 이 예제 기준으로 현재 큐가 3개(xque,yque,length)가 있는데 이 F의 중복 저장을 막음으로써 큐에 들어갈 데이터가 한개씩 줄어든다는것을 의미하고 그뜻은 다시말하면 메모리를 덜 사용한다는 뜻이다. 

이예제는 1개만 중복됬지만 사실 bfs를 돌리다 보면 더 많은 중복이 발생하기 때문에 이런식으로 꼭 중복을 막아야 시간내에,메모리 허용 범위 내에서 문제를 풀 수 있게 된다.

처음에 메모리 초과오류가 난 이유는

A의 자식으로 E D F 를 넣고 나서 A를 방문했다고 체크했기 때문에 오류가 났다.

이렇게 알고리즘을 짜게 되면

A가  E D F 자식을 넣고 나서 A를 방문했다고 체크하고 B로 돌아가서 마찬가지로 F G H를 자식에 넣기때문에 중복 방문이 발생한다.

전체코드

#include <iostream>

#include <algorithm>

#include <deque>

using namespace std;

int input[101][101];

int memo[101][101];

int n,m;

int diffx[4] ={-1,0,1,0};

int diffy[4] = {0,1,0,-1};

deque<int> xdeq;

deque<int> ydeq;

deque<int> length;

void bfs(int i,int j) //i,j는 bfs를 시작할 위치

{

    xdeq.push_back(i);

    ydeq.push_back(j);

    length.push_back(1);

    input[i][j] = 0; //큐에 시작점 넣고 시작점은 이미 방문했다고 표시후에 bfs를 시작함.

    while(xdeq.size() != 0)

    {

        

        int x = xdeq.front();

        int y = ydeq.front();

        int mark = length.front(); //현재 위치에 표시해야할 숫자

        xdeq.pop_front();ydeq.pop_front();length.pop_front(); //위치 방문

        

        memo[x][y] = mark++; // 위치를 방문해서 현재 땅에 시작점으로부터의 거리 표시

        for(int i=0; i<4; i++) //그다음 방문해야될 위치를 큐에 넣는다.

        {

            int nextX = x + diffx[i];

            int nextY = y + diffy[i];

            

            if(nextX >=1 && nextX <=n && nextY >=1 && nextY <=m && input[nextX][nextY] == 1)

            {

                xdeq.push_back(nextX);

                ydeq.push_back(nextY);

                length.push_back(mark);

                input[nextX][nextY] = 0;    //다음 방문할 위치를 넣으면서 동시에 그 위치는 방문했다고 표시함. 그래야 중복 방문을 막을 수 있다.

            }

        }

    }

}

int main()

{

    cin>>n>>m;

    

    for(int i=1; i<=n; i++)

    {

        for(int j=1; j<=m; j++)

        {

            scanf("%1d",&input[i][j]);

        }

    }

    

    bfs(1,1);

    

    cout<<memo[n][m]<<endl;

    

    

    return 0;

}