[BFS] 1697번 숨바꼭질

1697번 숨바꼭질

 

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는 정수이다.

 

출력

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

 

예제 입력

5 17

 

예제 출력

4

 

해결방법

이 문제는 N이 100,000이고 최소를 구하는 문제이다. 따라서 큐를 사용하는 BFS의 방법으로 문제를 풀 수 있다.

일단, 수빈이의 현재 위치가 주어진다. 이는 트리에서 시작 노드이다.

그 다음으로, 동생의 위치가 주어진다. 따라서 트리를 현재노드-1, 현재노드+1, 현재노드*2로 확장시키며 그릴 수 있다.

이런식으로 진행하다보면 동생의 위치에 대한 비용을 구할 수 있다.

이 문제는 단순하게 트리를 그려서 해당 위치의 dist[]만 구하면 되기 때문에 간단한 문제이다.

 

소스코드

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <queue>
#include <algorithm>
#define MAX 100000
using namespace std;

int n,k;
int ans;
bool visit[MAX+1];		// 노드 방문 여부를 체크하는 Flag
int dist[MAX+1];		// 노드로의 이동 비용을 저장하는 배열

bool isPossible(int x){
    if(x<0 || x>MAX)
        return false;
    return true;
}

// x-1 , x+1 , x*2 로 이동 가능
void bfs(int nn,int kk){
    queue<int> q;
    q.push(nn);
    visit[nn] = true;
    dist[nn] = 0;
    
    while(!q.empty()){
        int now = q.front();
        q.pop();
        
        if(isPossible(now-1) && !visit[now-1]){
            visit[now-1] = true;
            dist[now-1] = dist[now] + 1;
            q.push(now-1);
        }
        
        if(isPossible(now+1) && !visit[now+1]){
            visit[now+1] = true;
            dist[now+1] = dist[now] + 1;
            q.push(now+1);
        }
        
        if(isPossible(now*2) && !visit[now*2]){
            visit[now*2] = true;
            dist[now*2] = dist[now] + 1;
            q.push(now*2);
        }
    }
    ans = dist[kk];
}

int main(int argc, const char * argv[]) {
    memset(visit,false,sizeof(visit));
    scanf("%d %d",&n,&k);
    bfs(n,k);
    printf("%d",ans);
}