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

출처 : 12851번: 숨바꼭질 2 (acmicpc.net)

12851번: 숨바꼭질 2

풀이 방법

visited배열에 현재 위치를 방문했는지를 기록하고 하지 않았으면 bfs로 방문하면 된다

bfs를 이용하면 자동적으로 시간이 빠른 것부터 참 색 하여 답에 도착하므로 bfs를 사용하였다

x가 현재위치다. x-1 >=0 이고 x-1 지점을 방문하지 않았더라면 x-1 지점을 방문한다

여기서 현재 위치가 목표 위치보다 작더라도 x-1을 해주어야 한다 왜냐하면

예를 들어 현재위치가 7이고 목표 위치가 12이면 7에서 마이너스를 해 준후 곱하기 2를 한 것이 

빠른 시간내에 도착할 수 있기 때문이다.

또 현재 위치가 목표 위치보다 작은 경우에 현재 위치 + 1 지점을 방문한다

마지막으로 현재 위치가 목표 위치보다 작은 경우에 현재 위치 * 2할 지점을 방문한다.

기저 조건으론 현재위치가 목표지점이고 답을 찾지 못한 경우에는 답을 초기화

또 현재위치가 목표지점이고 지금까지의 답이랑 같은 시간일 경우 카운터를 +1 해주었다.

#include <bits/stdc++.h>

using namespace std;

int N,K, ans = 0, cnt = 0;
int visited[100001];
void bfs() {
    queue<pair<int, int>> q;
    q.push(make_pair(N, 0));
    while(!q.empty()) {
        int x = q.front().first;
        int sec = q.front().second;
        visited[x] = 1;
        q.pop();
        if (x == K && ans == 0) { // 초기답
            ans = sec;
            cnt = 1;
            continue;
        }
        if (x == K && ans == sec) { // 중복답
            cnt++;
            continue;
        }
        if (x - 1 >= 0 && visited[x-1] == -1) { 
            q.push(make_pair(x-1, sec+1));
        }
        if (x < K && x + 1 <= 100000 && visited[x+1] == -1) {
            q.push(make_pair(x+1, sec+1));
        }
        if (x < K && 2 *x <= 100000 && visited[2 * x] == -1) {
            q.push(make_pair(2 * x, sec+1));
        }

    }
}

int main() {
    cin >> N >> K;
    memset(visited, -1, sizeof(visited));
    bfs();
    cout << ans << endl <<cnt;
    return 0;
}