[백준 1697] 숨바꼭질

Queue를 사용한 BFS의 개념을 알고 있다면

쉽게 풀 수 있는 문제이다.

수빈이가 동생을 찾기 위해서 몇 번을 이동하는지 구하는 문제인데,

이동 할 수 있는 경로가

오직 세 가지 경우( now = 현재위치)

1. now - 1

2. now + 1

3. now * 2

밖에 없어서 배열을 사용하여 간단하게 구현이 가능하다.

(이때 수빈이와 동생의 위치가 같을 경우 '0'을 출력하는 경우를 예외로 처리해야한다)

출처 : https://www.acmicpc.net/problem/1697

문제

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

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

입력

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

출력

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

예제 입력 1

5 17

예제 출력 1

4

소스코드

#include<iostream>
#include<vector>
#include<queue>
 
using namespace std;
 
const int MAX = 100001;
 
int subin;        // 수빈의 위치
int sis;        // 동생의 위치
queue<int> q;
int cost[MAX];
bool check[MAX];
int ans = 1000000;
 
void solve(int now, int next){
    while(!q.empty()){
        now = q.front();
        q.pop();
        
        for(int i = 0; i < 3; i++){
            if(i==0 && (now - 1 >= 0))            next = now - 1;
            else if(i==1 && (now+1 <= MAX))        next = now + 1;
            else if(i==2 && (now*2 <= MAX))     next = now * 2;
            
            if(next >= 0 && next <= MAX){
                if(check[next] == false){
                    q.push(next);
                    check[next] = true;
                    cost[next] = cost[now] + 1;
                    if(next == sis)
                        ans = (ans > cost[next])? cost[next] : ans;
                }
            }
        }
    }
    return;
}
 
int main(){
    cin >> subin >> sis;
    
    check[subin] = true;
    q.push(subin);
    if(subin == sis)
        ans = 0;
    else
        solve(subin,0);
    cout << ans;
    return 0;    
}

※ 본 글은 개인 포트폴리오 혹은 공부용으로 사용하기 때문에, 무단 복사 유포는 금지하지만, 개인 공부 용도로는 얼마든지 사용하셔도 좋습니다.