백준 12851번, 숨바꼭질 2(C, C++)

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

12851번: 숨바꼭질 2

※잘못된 BFS

#include<iostream>
#include<queue>

using namespace std;
int dx[2]= {-1, 1};
queue<int> q;
bool visited[100001];
int N;
int K;

int BFS(int X, int cnt){
    visited[X] = true;
    queue<pair<int,int>> q;

    q.push({X, cnt});
    while(!q.empty()){
        int cur = q.front().first;
        int count = q.front().second;
        q.pop();

        if(K == cur){
            return count;
        }
        for(int i = 0; i < 3; i++){
            int next;
            if(i == 2){
                next = 2 * cur;
            }else{
                next = cur + dx[i];
            }

            if(next < 0 || next > K){
                continue;
            }

            if(!visited[next]){
                visited[next] = true;
                q.push({next, count+1});
            }
        }
    }
}

int main(){
    cin>>N>>K;

    cout<<BFS(N, 0)<<endl;
}

※올바른 BFS

#include<iostream>
#include<queue>

using namespace std;

queue<int> q;
bool visited[100001];
int N;
int K;
int A;
int first;
int cnt2;

int BFS(int X, int cnt){
 
    queue<pair<int,int>> q;

    q.push({X, cnt});
    while(!q.empty()){
        int cur = q.front().first;
        int count = q.front().second;
        q.pop();
        visited[cur] = true;  // 1 -> (1+1) = 2 -> (2*2) = 4인 경우와 (1*1) = 2 - > (2*2)= 4인 경우의 값이 같은 경우.

        if(first && cnt2 == count && K == cur){
            first++;
        }

        if(K == cur && first == 0){
            first++;
            cnt2 = count;          
        }
        if(cur + 1 <= 100000 && !visited[cur + 1]){
            q.push({cur+1, count+1});
        }
        if(cur - 1 >= 0 && !visited[cur - 1]){
            q.push({cur-1, count+1});
        }
        if(cur * 2 <= 100000 && !visited[2 * cur]){
            q.push({cur * 2, count + 1});
        }
        }
        return cnt2;
    }


int main(){
    cin>>N>>K;

    cout<<BFS(N, 0)<<endl;
    cout<<first;
}

이 문제는 너비 우선 탐색(BFS)를 사용해야합니다.

왜냐하면 최소한의 이동으로 동생에게 도착해야하기 때문입니다.

 

다만 일반적인 BFS문제와는 다른 점은 최소한의 이동으로 도착하는 방법을 카운트를 해주어야 합니다.

일반적인 BFS는 현재 위치에서 다음 위치로 갈 때 q.push()이후 바로 방문처리를 해주는 반면에,

이 문제에서는 q.pop()이후 바로 현재 위치를 방문처리를 해줍니다.

왜냐하면 1 -> (1+1 = 2)-> 2*2 = 4로 가는 방법과 1 -> (1*2=2) -> 2*2 = 4 가는 방법 2가지가 있기 때문입니다.

일반적인 BFS로 방문처리할 시, 처음 방법 (1+1 = 2)은 visited[2] = true가 되어있기 때문입니다.

 

위 코드는  다음 이동할 곳을 방문처리하는 것이 아닌, 현재 위치를 방문처리하게 되면

 

다른 방식으로 이동하는 경우의 방문처리와 부딪힐 일이 없게 되는 것 입니다.