#1697 백준 숨바꼭질 코드 C++

1697번: 숨바꼭질

 

백준 1697번 숨바꼭질 문제이다.

 

백준에는 숨바꼭질 시리즈의 문제가 많은데, 

이전 문제는 그리디, DP등 다양한 알고리즘으로 해결이 가능했다.

이 문제 역시 여러 해결 방안이 있지만

타겟 알고리즘은 너비우선탐색(BFS)이다.

 

문제에서 주어진 예시를 보면 수빈이의 위치는 5이고 동생의 위치는 17이다.

수빈이는 1초후에 위치-1, 위치+1, 위치*2 의 위치로 이동할 수 있다.

5의 경우, 4, 6, 10 으로 이동할 수 있는 것이다.

 

이동 가능한 4, 6, 10은 모두 동생이 있는 위치 17이 아니기 때문에 다시 한번 위의 과정을 반복한다.

4로 이동했을 경우, 3, 5, 8로 이동할 수 있지만, 5는 이미 간 곳이기 때문에 가지 않는다.

6의 경우도 7, 12를 방문하고, 10은 9, 11, 20을 방문 처리한다.

이러한 과정을 반복해서 17이 나오면 반복의 횟수를 출력한다.

 

아래는 C++로 작성한 코드 전문이다.

 

#include <iostream>
#include <queue>

using namespace std;

int cnt = 0;
bool visited[100001] = {false, };

void bfs(int start, int k) {
    queue<int> q;
    q.push(start);
    visited[start] = true;

    while(!q.empty()) {
        int size = q.size();
        for(int i = 0; i < size; i++) {
            int num = q.front();
            q.pop();
            if(num == k)
                return;
            if(visited[num+1] == false && num + 1 >= 0 && num +1 <= 100000) {
                visited[num+1] = true;
                q.push(num+1);
            }
            if(visited[num-1] == false && num - 1 >= 0 && num - 1 <= 100000) {
                visited[num-1] = true;
                q.push(num-1);
            }
            if(visited[num*2] == false && num*2 >= 0 && num*2 <= 100000) {
                visited[num*2] = true;
                q.push(num*2);
            }
        }
        cnt++;
    }
}

int main() {
    ios::sync_with_stdio(0);cin.tie(0);
    int n, k;
    cin >> n >> k;
    bfs(n, k);
    cout << cnt << "\n";
    return 0;
}