[백준] 12851 숨바꼭질 2

문제 설명

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

12851번: 숨바꼭질 2

수빈이는 점 N(0 <= N <= 100000)에 있고, 동생은 점 K(0 <= k <= 100000)에 있을 때, 수빈이는 1초 후에 x - 1, x + 1, x * 2의 위치로 이동할 수 있다

동생이 있는 위치로 이동하는 가장 빠른 시간과, 가장 빠른 시간으로 동생을 찾는 방법의 수 구하기

 

문제 풀이법

최단거리를 찾는 문제이므로 BFS를 사용하여 풀 수 있다

 

가장 빠른 시간을 찾는 1697번 숨바꼭질 문제와는 다르게, 가장 빠른 시간으로 동생을 찾는 방법의 수도 구해야하기에 방법이 조금 다르다

 

arr를 방문했는지 여부를 확인하는 배열로 선언하고, 초기값을 0으로 선언 후 방문했으면 1로 설정한다

queue<pair<int, int>>로 선언한다

• 첫번째 int : 현재 수빈이의 위치
• 두번째 int : 수빈이가 이동한 시간

 

중요하게 살펴봐야할 것이 이부분이다

가장 빠른시간으로 수빈이가 동생을 찾는 방법의 수를 세야 하기 때문에, 처음으로 동생을 만나면 최소 시간으로 셋팅해준다

이후에 또다른 동생을 만나는 방법이 생기면, 그 방법이 최소시간인지 확인 후 만난 방법의 수를 세준다

//동생을 만났고, 처음으로 동생을 만나지는 않았지만 만난 시간이 최소 시간과 같을 때
if (cnt != 0 && x == k && time == min)
        cnt++;
    
//처음으로 동생을 만났을 때
if (cnt == 0 && x == k)
{
    min = time;
    cnt++;
}

 

소스 코드

#include <iostream>
#include <queue>

using namespace std;

int main()
{
    int n, k;
    int arr[100001];
    
    cin >> n >> k;
    
    queue<pair<int, int>> q;
    
    fill(arr, arr + 100001, 0);
    
    q.push({n, 0});
    
    int min = 0;
    int cnt = 0;
    
    while (!q.empty())
    {
        int x = q.front().first;
        int time = q.front().second;
        
        q.pop();
        arr[x] = 1;
        
        if (cnt != 0 && x == k && time == min)
            cnt++;
        
        if (cnt == 0 && x == k)
        {
            min = time;
            cnt++;
        }
        for (int nx : {x - 1, x + 1, 2 * x})
        {
            if (nx < 0 || nx > 100000)
                continue;
            if (arr[nx] == 1)
                continue;
            q.push({nx, time + 1});
        }
    }
    
    cout << min << "\n";
    cout << cnt;
    
    return 0;
}