[algorithm] 백준 - 숨바꼭질 2

이 문제는 숨바꼭질 문제와 이어지는 bfs 문제이다.

추가되는 부분은 가장 빠른 시간으로 찾는 방법이 몇가지인지 구해야한다는 것이다.

 

예를 들어 수빈이는 1 에 위치해 있고 동생은 4에 있다고 가정하면,

가장 빠른 시간으로 찾기 위해선 여러 경우로 가지가 뻗어나갈 때,

동일한 시간에 두가지 방법이 있다는 것을 알 수 있다.

 

만일 queue에 값을 넣을 때 방문여부를 체크하게 된다면 1+1이나 1*2 중 가장 먼저 값이 넣어지는 경우의 방법만 찾을 수 있게 된다.

그러므로, queue에 값을 넣을 때 방문여부를 체크하지 말아야한다.

 

그렇다고 모든 방문 여부를 체크하지 말아야할까?

 

아니다, 방문 여부는 반드시 체크해야한다. 그러지 않으면 숨바꼭질은 끝나지 않는다.

 

그럼 방문 여부는 언제 체크해야할까? 최소 시간으로 방문된 지점을 통과했을 때부터 체크해야한다.

 

최소 시간으로 방문된 지점을 통과하는 건 어느 시점일까?

가장 처음 queue에서 빠져나온 동생의 위치에 도달한 시간이 최솟값이다.

이 순간에 방문 여부를 체크해야한다. 이후엔 queue에 넣을 필요는 없다.

그 이후로 동생의 위치에 도달한 시간이 최솟값과 동일하다면 count를 증가시킨다.

        if(point == k && !visited[point]){
            minWeight = weight;
            minCount++;
        }
        if(point == k && visited[point] && weight == minWeight){
            minCount++;
        }
        visited[point] = true;

 

 

 

 

나머지 코드는 숨바꼭질 문제와 동일하다는 것을 알 수 있다.

//숨바꼭질 2
#include <iostream>
#include <queue>
using namespace std;
bool visited[100001];
int minCount = 0, minWeight = 0;
void bfs(int n, int k){
    queue<pair<int,int>> q;
    q.push({n,0});
    visited[n] = true;
    while(!q.empty()){
        pair<int,int> node = q.front();
        int point = node.first;
        int weight = node.second;
        q.pop();
        if(point == k && !visited[point]){
            minWeight = weight;
            minCount++;
        }
        if(point == k && visited[point] && weight == minWeight){
            minCount++;
        }
        visited[point] = true;
        if(point * 2 >= 0 && point * 2 <= 100000 && !visited[point * 2]){
            q.push({point*2,weight+1});
        }
        if(point - 1 >= 0 && point - 1 <= 100000 && !visited[point - 1]){
            q.push({point - 1, weight+1});
        }
        if(point + 1 >= 0 && point + 1 <= 100000 && !visited[point + 1]){
            q.push({point + 1, weight +1});
        }
    }
}
int main(void){
    int n,k;
    cin >> n >> k;
    fill_n(visited, 100001, false);
    bfs(n,k);
    cout << minWeight << "\n" << minCount;
}