숨바꼭질 3

알고리즘 구분 : BFS

문제

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

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

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

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

예제 입력 1
5 17
예제 출력 1
2

문제 풀이

처음에는 DFS와 같이 재귀 형태로 접근하고자 하였으나, 명확한 종료 조건을 설정하는 것에 어려움이 있어, 해당 방식을 사용할 수 없다고 판단하였다.
그렇기에, BFS를 활용해서 구현하도록 하였다. Queue를 생성한 뒤, 특정 위치까지 도달하는 시간을 갱신이 가능한 상황이라면, 갱신을 진행하고, Queue에 해당 위치를 push하여 해당 위치에 다른 위치까지 이동하는 데 걸리는 시간을 갱신할 수 있도록 구현하였다.

소스 코드

#include <bits/stdc++.h>

using namespace std;

int n, k;
int visited[100001];
void bfs(int start);

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n >> k;
	
	fill(visited, visited + sizeof(visited)/sizeof(int), 987654321);
	
	bfs(n);
	
	cout << visited[k] << endl;
	
	return 0;
}

void bfs(int start) {
	int now, move, temp;
	int dir[] = {-1, 1, 2};
	queue<int> q;
	
	q.push(start);
	visited[start] = 0;
	while(!q.empty()) {
		now = q.front();
		q.pop();
		
		for(int i = 0; i < 3; i++) {
			if(i == 2) {
				move = now * dir[i];
				temp = visited[now];
			}
			else {
				move = now + dir[i];
				temp = visited[now] + 1;
			}
			
			if(0 > move || move > 100000) {
				continue;
			}
			
			if(visited[move] > temp) {
				visited[move] = temp;
				q.push(move);
			}
		}
	}
}

• 문제 출처 : https://www.acmicpc.net/problem/13549
• 해당 풀이는 백준에서 "맞았습니다!!" 판정을 받았습니다.