[백준] 숨바꼭질_1697번

[백준] 숨바꼭질

문제

링크 : BOJ

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

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

---

---

풀이

수빈이가 동생을 찾을 때 시간 당 갈 수 있는 방법의 수는 3가지이다. 이 3가지를 구현하고 3가지 중 하나라도 이행했을 때, 시간이 1 증가하게 된다. 따라서 {행동, 시간} 순으로 쌍을 이뤄 q에 저장한다.

그리고 각 행동마다 시간이 달라지므로 너비 우선 탐색을 해서 중복해서 방문했던 경우와 범위 밖으로 갔을 경우는 포함시키지 않는다.

결과는 다음과 같다.

#include <iostream>
#include <queue>
using namespace std;
int N, K;
int t = 0;
bool visit[100001] = { false };

queue<pair<int, int>> q;
int bfs()
{
	visit[q.front().first] = true;
	while (!q.empty())
	{
		int p = q.front().first + 1;
		int m = q.front().first - 1;
		int x = q.front().first * 2;
		int t = q.front().second + 1;
		if (p == K || m == K || x == K)
		{
			return t;	
		}
		q.pop();

		if (x < 100001 && !visit[x])
		{
			q.push({ x, t });
			visit[x] = true;
		}

		if ( p < 100001 && !visit[p])
		{
			q.push({ p,t });
			visit[p] = true;
		}

		if (m >= 0 && !visit[m])
		{
			q.push({ m, t });
			visit[m] = true;
		}
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie();


	cin >> N >> K;
	if (N == K)
	{
		cout << 0 << endl;
		return 0;
	}
	q.push({ N, t });
	cout << bfs() ;
	return 0;
}

---

실수했던 점

계속 런타임 오류가 떴었는 데, 그 이유를 찾지 못해 고생했었다. 그 이유는 보통 범위 바깥에 있는 배열을 지정하면서 검사를 했기 때문이다.

범위 바깥에 있을 경우 예외를 시켜줬긴 했는데, 그 전에 배열에서 먼저 확인을 해버리면 버그가 뜨게 된다.

 if (x < 100001 && !visit[x])
 if ( p < 100001 && !visit[p])
 if (m >= 0 && !visit[m])

이 부분에서 visit배열의 위치를 앞으로 했더니 이미 확인을 하고 있는 상태이기 때문에 런타임 오류가 뜨게 된 것이었다… 배열을 사용할 땐, 이 부분을 조심해서 쓰자.

---