[백준 1697번] 숨바꼭질 C++

www.acmicpc.net/problem/1697

1697번: 숨바꼭질

5014번 스타트 링크랑 비슷한 문제입니다.

 

한 번의 BFS 때마다 -1, +1 , *2 << 이 세가지의 경우를 동시에 수행합니다.

cnt배열은 각 인덱스의 위치에 있을때, 거기로 갈 수 있는 최소의 이동횟수를 기록합니다.

 

if (way[i] >= 0 && way[i] <= 100000 && cnt[way[i]] == 0)

이 부분을 보면 cnt가 0일때, 즉 한번도 이 곳에 가는 횟수를 기록한 적이 없을때만 탐색을합니다.

 

만약 1에서 4라는 위치로 이동을 하기위해서는

+1 +1 +1  < 총 3번의 이동

*2  +1       <총 2번의 이동

 

어짜피 bfs에서는 한 번에 3가지 가능한 이동을 모두 해볼 수 있기 때문에

무조건 처음 도착할때 소모한 횟수가 최소값이됩니다.

즉 다음번에 다시 방문할때 소모한 횟수가 나온다면 무조건 초기값보다는 큰 값이므로 저장하거나 방문할 필요가 없습니다.

 

 

#include <iostream>
#include <queue>
 
using namespace std;
 
int n, k;
int cnt[100001];
queue<int> q;
 
int bfs() {
    q.push(n);
 
    while (!q.empty()) {
        int subin = q.front();
        q.pop();
        //탈출조건
        if (subin == k)
            return cnt[subin];
        //수빈이 이동할 수 있는 방법 3가지를 배열화
        int way[3] = { subin + 1, subin - 1, 2 * subin };
 
        for (int i = 0; i < 3; i++) {
            if (way[i] >= 0 && way[i] <= 100000 && cnt[way[i]] == 0) {
                q.push(way[i]);
                cnt[way[i]] = cnt[subin] + 1;
            }
        }
    }
}
int main() {
    cin >> n >> k;
    
    cout << bfs();
    return 0;
}