[ 백준 12851 ] 숨바꼭질 2 (c/c++)

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

 

 

[ 문제 요약 ]

수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하고 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동한다. 수빈이의 위치와 동생의 위치가 주어질 때 수빈이가 동생을 찾는 가장 빠른 시간과 동생을 찾는 방법의 수를 출력한다.

 

 

[ 문제 풀이 ]

1. BFS를 통해 수빈이가 동생을 찾는 가장 빠른 시간을 구할 수 있다.

2. 이 시간을 저장해두고 BFS의 결과에서 시간이 동일하다면 방법의 수를 추가한다.

 

 

[ 소스 코드 ]

#include <bits/stdc++.h>
using namespace std;

int N, K, t = 101010, ans = 0;
int visited[101010];
bool fir = true;
queue<pair<int, int>> q;

void BFS(int a, int b){
    q.push(make_pair(a, b));
    visited[a] = 1;

    while (!q.empty()){
        int x = q.front().first;
        int cnt = q.front().second;
        q.pop();
        visited[x] = 1;

        if (!fir && t == cnt && x == K) ans++;
        if (fir && x == K){
            t = cnt;
            fir = false;
            ans++;
        }
  
        int go[3] = { x - 1, x + 1, x * 2 };
        for (int i=0; i<3; i++){
            if (go[i] < 100001 && go[i] >= 0 && !visited[go[i]]){
                q.push(make_pair(go[i], cnt + 1));
            }
        }
    }
}

int main() {
    cin >> N >> K;
    BFS(N, 0);
    cout << t << "\n" << ans;
    return 0;
}

 

 

[ 주의할 점 ]

한 번에 두가지 변수를 다뤄야 하기 때문에 큐를 페어로 만들어야 한다.