[C++] 백준 알고리즘 13549 숨바꼭질 3 (0-1 BFS)

13549번: 숨바꼭질 3 (acmicpc.net)

13549번: 숨바꼭질 3

7%, 90%에서 멈추는 사람 .... 🖐 ^^

나밖에 없을듯,..

 

0-1 BFS

우선 0-1 BFS란? 최단경로 문제이면서 가중치가 0,1 만 존재할 때 덱을 이용하여 푸는 문제이다. 다익스트라를 사용했을 때 보다 빠르다.

가중치가 두 개인 상태에서 최단경로를 구해야하므로

가중치가 낮은걸 push_front를 하고 가중치가 높은걸 push_back하면 우선순위(짧은 경로)에 따라 탐색할 수 있다.

 

방문 확인

중복 방문을 방지하기 위해 방문을 체크하는 배열이 필요하다.

BFS의 특징은 가장 먼저 방문한 것이 최단 경로라는 보장이 있으므로

"뒤에 나오는 값이 최단 경로인데 앞에서 방문 체크를 해서 뒤에 나오는 경로를 탐색하지 못하면 어쩌지?" 라고 생각하지 않아도 된다.

 

방문 체크를 위해 많은 사람들이

정답을 저장할 int time 변수와 bool visit 배열을 나눠서 쓰는 걸 봤다.

혹은 pair 에 시간과 정점을 저장하는 방법도 있었다.

이 두 값을 합쳐서 int check 배열에 time 값을 저장하며 탐색하면 좋을 것 같다고 생각했다.

그런데 이렇게 탐색한 코드들을 보면, 탐색해야하는 수가 n일 때 check[n]=1 로 초기화를 했다. 그 다음 원하는 값에 도달하여 return을 할 때 check[n] -1 을 하는 것을 봤다. (t초가 지났을 때 check[n]=t+1 이 되므로)

 

여기서 그냥 check[n]=0으로 하면 출력할 때 -1을 하지 않고 check[n]만 출력해도 되지 않을까? 라는 생각을 하게되었다.

그런데 많은 사람들이 하지 않은데에는 이유가 있었다.

 

check[n]=0 으로 했을 때 생기는 문제 1 : 7%에서 시간초과

바로 n=0일 때를 고려하지 못했기 때문이다.

n=0일 경우 0*2=0이므로 덱의 맨 앞에는 0만 쌓이게 된다. 그러면서 무한 루프에 빠진다. 그렇기 때문에 시간초과가 나오는 것이다.

이를 해결하기 위해 순간이동하는 if문 안에 x!=0 이라는 조건을 추가했었다. (부질없는 짓이었다)

 

check[n]=0 으로 했을 때 생기는 문제 2 : 90%에서 틀렸습니다

90%에서 틀렸습니다가 나왔는데 아무리 생각해도 반례를 찾기가 힘들었다. 그래서 엄청 오래 고민했는데.... 반례는 찾지 못했지만, check 배열의 초기화와 연관된 문제라는 것을 깨달았다.

 

어디에서 문제가 생긴거였나면... 처음 주어진 값이 5일 때 -1을 하게 되면 4이다. 그리고 덱에서 4를 꺼내서 탐색할 때 +1 을 하는 구문을 지나면 5가 덱에 들어가게 된다. 왜냐면 내 방식대로 하면 초기 값 5는 check[5]=0 인 상태 그대로라서 if문을 수행하니까!!

5 ...(생략)... 4 ...(생략)... 5 ... 이렇게 나의 초기 위치가 또 덱에 들어가는 불상사가 일어난다 ㅠ ㅠ

 

check배열에는 시간이 들어간다는 것에 집착해서 이런 문제가 생겼다.

그런데 너무 말도안되는 실수였어서 나같은 실수를 한 사람은 없을 것 같다..

 

그래서 check배열 전체를 -1로 초기화를 해주고 if문 안의 조건을 (    !check[x]   ->   check[x]==-1     ) 로 바꾸어주면 해결이 된다.

그런데 이 방법 보다는 그냥 check[n]=1 로 초기화를 해주고 check[n]-1 을 리턴해주는게 가장 마음 편하다 ^^

 

오늘의 교훈 : 많은 사람들이 그렇게 한 데에는 이유가 있다

 

#include <iostream>
#include <deque>
#include <vector>

// 0-1 BFS문제
// 최단거리 문제이지만 가중치가 0,1일 때는 다익스트라 말고 0-1 BFS로 풀이할 수 있다.
// 덱 deque를 이용하고, 가중치가 0인걸 우선순위로 두기 때문에 앞에 넣으면 되고
// 가중치가 1인것은 우선순위가 낮기 때문에 뒤에 넣는다.

using namespace std;

const int SIZE = 100001;

int zeroOneBFS(int n, int k){
    vector<int> check(SIZE,0); //방문 확인 & 소요 시간 저장
    deque<int> dq;

    check[n]=1;
    dq.push_back(n);

    while(!dq.empty()){
        int x=dq.front();
        dq.pop_front();

        if(x==k)
            return check[x]-1;

        //순간이동
        if(x*2<SIZE && !check[x*2]){
            dq.push_front(x*2);
            check[x*2]=check[x];
        }

        //앞으로 걷기
        if(x+1<SIZE && !check[x+1]){
            dq.push_back(x+1);
            check[x+1]=check[x]+1; //1초 증가
        }

        //뒤로 걷기기
        if(x-1>=0 && !check[x-1]){
            dq.push_back(x-1);
            check[x-1]=check[x]+1; //1초 증가
        }
    }
}

int main(){
    int n,k;
    cin>>n>>k;
    cout<<zeroOneBFS(n,k)<<'\n';
}