백준 1697 숨바꼭질 - C++

 

접근

해당 문제는 BFS로 쉽게 접근할 수 있다.

BFS나 DFS나 모든 정점을 1번만 방문하는 알고리즘인데 BFS는 간선의 가중치가 1이라는 조건일 때 최단 거리 구하는 문제에 응용할 수 있다.

 

문제에서 보면 어떤 정점 N에서 N-1, N+1, N*2의 정점에 도달하는데 걸리는 시간이 1이라고 한다.

여기서 시간 1은 정점과 정점을 연결하는 간선의 가중치가 될 수 있다. 

 

문제는 다음과 같이 순차적을 처리 될 수 있다.

 

1. N과 K의 정점 입력

2. N을 큐에 푸쉬, N 방문 표시, N의 거리 표시

3. 큐가 빌 때까지 계속 돌기

4. 큐에서 한 정점을 빼서 이동 가능한 정점의 노드를 만든다.

5. 이동 가능 정점이 이동가능한 거리에 있는지 조건 확인 후 큐에 푸쉬, 방문 표시, 거리 표시를 한다. 

6. 모든 정점 방문 시 K정점의 거리 출력

 

#include <iostream>
#include <queue>
using namespace std;

const int nodeLimit = 200000;
bool check[nodeLimit+1];
int dist[nodeLimit+1];

int main(){
    int N,K;
    cin >> N >> K;
    
    queue<int> q;
    q.push(N); check[N] = true; dist[N] = 0;
    while(!q.empty()){
        int node = q.front(); q.pop();
        int backNode = node - 1;
        int forwardNode = node +1;
        int multiplyNode = node * 2;
        if( backNode >= 0 && check[backNode] != true){ 
            q.push(backNode); check[backNode] = true; dist[backNode] = dist[node] +1;
        }
        if( forwardNode < nodeLimit && check[forwardNode] != true) {
            q.push(forwardNode); check[forwardNode] = true; dist[forwardNode] = dist[node] +1;
        }
        if(multiplyNode < nodeLimit && check[multiplyNode] != true){
            q.push(multiplyNode); check[multiplyNode] = true; dist[multiplyNode] = dist[node] +1;
        }
    }
    cout << dist[K] << '\n';
    return 0;
}

 

여기서 nodeLimit이 100000이 아니라 200000으로 넉넉하게 잡은 이유는 

만약에 N이 50001이고 K가 100000일 때 N*2정점으로 이동 후 N-1 정점으로 몇번 이동하면 쉽게 K의 정점에 도달할 수 있기 때문