[백준 알고리즘] 1697번: 숨바꼭질
May 05, 2020
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는 정수이다.
출력
수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
풀이
BFS를 통해서 해결했다. 첫 시작점으로 부터 진행할 수 있는 경우가 -1, +1, X2 총 세 가지가 있다. 즉 시작점이 트리의 루트노드라고 한다면, 해당 루트로부터 세개의 자녀 노드들이 나오는 것이다. 그리고 각 자녀노드들은 새로운 서브트리의 루트노드가 되어서 또 다른 세 경우의 자녀 노드를 만든다. 따라서 bfs 로 계속 진행하다가 끝나는 지점의 값이 나오게 되면 해당 노드의 level 이 거리가 된다.
bfs의 큐를 페어로 만들어서 각 노드들의 깊이 혹은 레벨을 기록하고 끝나는 값을 가진 노드의 레벨을 출력해준다.
코드
#include <cstdio>
#include <queue>
#include <utility>
using namespace std;
int visited [100001] = {0,};
int bfs(int N, int K){
queue<pair<int, int>> q;
q.push(make_pair(N, 0);
while(!q.empty()){
pair<int, int> v = q.front();
if(v.first == K) break;
q.pop();
if(!visited[v.first]){
if (v.first+1 <= 100000) q.push(make_pair(v.first+1, v.second+1));
if (v.first-1 <= 100000) q.push(make_pair(v.first-1, v.second+1));
if (v.first*2 <= 100000) q.push(make_pair(v.first*2, v.second+1));
visited[v.first] = true;
}
}
return q.front().second;
}
int main (){
int N, K;
scanf("%d %d", &N, &K);
printf("%d", bfs(N, K));
}
