C++) 백준 13549 숨바꼭질3

문제

 

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

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

 

 

코드

 

#include <iostream>
#include <climits>
#include <queue>

using namespace std;

bool vis[100002];

int main()
{
	queue<pair<int, int>> Q;	// 위치/시간
	int minTime = INT_MAX;
	int n, k;

	cin >> n >> k;

	if (n >= k) {
		cout << n - k;		// 그리디
		return 0;
	}

	Q.push({ n,0 });

	while (!Q.empty()) {

		int x = Q.front().first;
		int t = Q.front().second;
		Q.pop();

		vis[x] = true;

		if (x == k && t < minTime) minTime = t;

		if (vis[k]) continue;	// 더 이상 큐에 들어가지 못함

		for (int nxt : {x - 1, x + 1, x * 2}) {

			if (nxt < 0 || nxt > 100000) continue;
			if (vis[nxt]) continue;

			if (nxt == x * 2)
				Q.push({ nxt, t });
			else
				Q.push({ nxt, t + 1 });
		}
	}
	cout << minTime;
}

 

 

풀이

 

<접근1>

기존의 '큐에 빨리 도착하기' 와는 다르게 '시간' 조건이 생겨 빨리 도착해도 더 살펴야 하는 경우로 중복을 허용해야 한다.

 

<접근2>순간이동(x2) 시 0초이기 때문에 먼저
'다른 경우보다 동생과 만나는 시점은 늦더라도 걸린 시간은 더 짧은 경우' 를 생각해보았다.
여러 경우를 들었을 때, 최소 같거나 느릴 수 밖에 없었다.
( 같은 경우 ex. 0 3)

 

그래서 분기가 같을 때만을 생각해보았다.
같은 분기점 (  - 1로 이동 or + 1로 이동 or x 2로 이동하기 전의 시점에 존재하는 큐의 원소들)
에서는 입력 '0 2'를 예로 들면

 

0  +1  1  +1  2  -> 2초
0  +1  1  x2  2  -> 1초

 

로 늦게 도착했어도 걸린 시간이 빠른 경우가 있다.
같은 분기까지만 비교하기 위해 pop후 방문 처리를 하며 동생 위치를 방문했을경우 큐에 삽입되지 않도록 처리했다.

 

 

+

 

재밌는 글을 하나 보았다.

 

먼저 도착한 경우 바로 해당 도착의 걸린 시간을 출력하고 끝내는 코드를 짠 경우
반복을 돌릴 때 X x 2, X - 1, X + 1이 아닌 X x 2, X + 1, X - 1 로 한다면 틀린 답이 나온다는 글에 달린 답변이다.
내가 푼 코드의 경우는 해당되지 않았지만, 좋은 정보인 것 같아 가져와 보았다.