[백준] 숨바꼭질 3 (13549번)

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 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

힌트

수빈이가 5-10-9-18-17 순으로 가면 2초만에 동생을 찾을 수 있다.

---

숨바꼭질 2 보다 더 쉬운 문제이다. 숨바꼭질 1에서 순간이동을 할 때 시간이 소요 안 된다는 점만 바뀌었다. 

따라서 다음 지점이 2*x 일땐 dist[nx] = dist[x]로만해주면 해결할 수 있다. 

저번 포스트에서 알아낸 for문을 이용해서 문제를 풀었다. for(int nx : {x-1, x+1, 2*x}) 부분이다. 확실히 조건을 일일이 쓰는 것 보다 이렇게 반복문으로 묶어서 하니까 더 편하다.

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/%EC%88%A8%EB%B0%94%EA%BC%AD%EC%A7%883(13549).cpp

chosh95/STUDY

C++ 코드

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int dist[100001];
int N, K;

void bfs()
{
	queue<int> q;
	q.push(N);
	dist[N] = 0;
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		if (x == K) return;
		for (int nx : {x - 1, x + 1, 2 * x}) {
			if (nx < 0 || nx>100000) continue;
			if (dist[nx] > dist[x] + 1) {
				if (nx == 2 * x) dist[nx] = dist[x];
				else dist[nx] = dist[x] + 1;
				q.push(nx);
			}
		}
	}
}
int main()
{
	cin >> N >> K;
	for (int i = 0; i <= 100000; i++) dist[i] = 987654321;
	bfs();
	cout << dist[K];
}