[백준 13549번 숨바꼭질 3] 문제 풀이

문제 사이트 : https://www.acmicpc.net/problem/13549

 

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

 

- 해결 아이디어 

• 큐를 이용해서 BFS 구현
• 시간 배열을 만들어서 각 지점까지의 최소 시간을 저장
• 방문 배열을 만들어서 각 지점의 방문 여부를 체크
• 순간이동은 시간이 소요되지 않으므로 걷기보다 먼저 처리하고 유효위치보다 작으면 2배를 계속 반복해서 큐에 삽입한다. 반복이 다 끝난 이후에 +1, -1 걷기를 처리한다.
  
  • 유효위치는 K + (K-N), 유효위치를 넘어서면 N에서 K까지 단순 걷기를 했을 때보다 시간이 많이 걸리기 때문에 더 계산할 의미가 없음

- 해결 방법

1. 처음 시작 위치를 큐에 삽입

2. 큐를 pop해서 현재 위치를 가져옴

3. 현재 위치에서 {*2, -1, +1} 순서로 연산을 해 유효 범위안에 있거나 방문하지 않은 위치라면 큐에 삽입하고 시간 배열 요소에 현재 위치의 최소 이동 횟수에 + 1.

단 *2 연산은 해결 아이디어 4번처럼 처리하고 최소 이동 횟수를 현재 위치의 최소 이동 횟수를 그대로 대입.

4. 2,3번 방법 반복하다가 큐가 비거나 K 위치를 방문한다면 bfs를 종료하고 K 위치의 최소 이동 횟수를 반환

예외) N이 K보다 크거나 같은 경우 반복하지 않고 바로 N-K를 반환한다.

 

// 백준 문제 : 숨바꼭질3

#include <iostream>
#include <queue>

using namespace std;

int dx[3] = {0,-1,1};
int N,K;
vector<int> dist(200002,0);
vector<bool> visited(200002,false);
queue<int> qu;

int bfs(){
    if(N >= K){
        return N-K;
    }
    qu.push(N);
    visited[N] = true;
    while(!qu.empty()){
        int x = qu.front(); qu.pop();
        // cout << "큐 반복 : " << x << endl;

        if(visited[K] == true){
            return dist[K];
        }
        for(int i=0;i<3;i++){
            int cx;
            if(i == 0){
                cx = x*2;
                while(cx < K + (K-N)){
                    if(visited[cx] == false){
                        // cout << cx << endl;
                        dist[cx] = dist[x];
                        visited[cx] = true;
                        qu.push(cx);
                        cx *= 2;
                    } else {
                        break;
                    }
                    
                }
                continue;
            } else {
                cx = x + dx[i];
            }

            
            if(cx >= 0 && cx < K+(K-N) && visited[cx] == false){
                dist[cx] = dist[x]+1; 
                visited[cx] = true;
                qu.push(cx);
                // cout << cx << endl;
            }
        }
    }
    return -1;
}

int main(){
    cin >> N >> K;

    cout << bfs() << endl;
}