알고리즘 :: 백준 :: BFS :: 1697 :: 숨바꼭질

문제

문제접근

문제 이해

• Greedy유형으로 오해할 수 있는 문제입니다.
  임의의 점을 향할 때 반드시 순간이동을 사용하는 것이 유리하지는 않습니다.

  • 예를 들어, 5에서 17로 갈 때, 5 -> 10 -> 20 -> 19 -> 18 -> 17 보다
    5 -> 10 -> 9 -> 18 -> 17이 1초 더 빠릅니다.

• 최단 시간, 최단 거리를 찾아야 하는 문제이므로 직관적으로 BFS를 떠올릴 수 있습니다.

• 행동은 세 가지입니다.

  1. 한 칸 앞으로 이동 X + 1
  2. 한 칸 뒤로 이동 X - 1
  3. 순간이동 2 * X

• 임의의 점 x에 대한 세 가지 액션을 queue에 넣고 방문표시를 합니다.

  Q. 이 문제는 그래프 문제가 아닌데도 방문표시를 해야하나요?

  A. 네, 이 문제도 방문표시를 해야만 중복검사를 피할 수 있습니다. 임의의 점 x에 대해 취할 수 있는 세 가지 액션에 대해서 모두 표현했기 때문에 다른 경우로 x에 도착했을 때 또다시 세 가지 액션을 queue에 넣는 것은 중복검사입니다.

• 이 문제에서 가장 주의해야 할 점은 메모리 초과입니다.
  메모리 초과를 막기 위한 방법으로 두 가지를 사용합니다.

  1. 방문표시로 중복검사를 피합니다. (queue에 중복된 점을 넣지 않습니다.)
  2. 다음에 방문할 점이 0과 100,000을 넘지 않도록 검사합니다.

코드

#include <iostream>
#include <queue>
#define MAX 100000
using namespace std;

int N, K;
bool visited[100001];
/* visit 표시를 하는 이유
이미 방문한 위치는 queue에 들어가서 순회할 것이므로
다시 queue에 넣는 것은 중복 검사가 되기 때문이다. */
int solve() {
	queue<pair<int, int>> q;
	q.push({N, 0});
	visited[N] = true;
	
	while (!q.empty()) {
		int cPos = q.front().first, cSec = q.front().second;
		if (cPos == K) return cSec;
		q.pop();
		int nPos1 = cPos * 2, nPos2 = cPos - 1, nPos3 = cPos + 1, nSec = cSec + 1;
		if (nPos1 <= MAX && !visited[nPos1]) q.push({nPos1, nSec}), visited[nPos1] = true;
		if (nPos2 >= 0 && !visited[nPos2]) q.push({nPos2, nSec}); visited[nPos2] = true;
        if (nPos3 <= MAX && !visited[nPos3]) q.push({nPos3, nSec}); visited[nPos3] = true;
	}
	return -1;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> N >> K;
	cout << solve() << '\n';
}

결과