13549 숨바꼭질 3

꽤 고민한 문제였고, 질문 검색으로 힌트를 얻을 수 있었는데 문제가 된 부분은 다음과 같다.

1. BFS를 통한 최단거리를 구하려 했으나, 오답이라고 뜸
   • 문제에서 순간이동하는 경우에 시간이 0초가 걸리기 때문에 가중치를 고려해야 함
   • BFS 최단거리는 가중치가 동일하다는 가정하에 정상 동작하기 때문에 오답
     • 조금 더 생각해보면, 반복문에서 N == K일 때 종료되기 때문에 순간이동으로 도달하지 않은 경우 최단거리가 아님을 알 수 있다.
2. 가중치를 적용하여 우선순위 큐를 돌리면 시간이 오래걸림
   • 디버깅한 결과, 연산 개수가 많아서 시간이 오래걸리는 걸로 보여, 다음과 같이 수정했다.
     • 우선순위 큐 대신 덱(deque)를 사용하여 순간이동 하면 push_front를 하도록 했다.
     • N > K인 경우, *2 +1 연산이 무의미하기 때문에 -1만 하도록 했다.
   • 10만개의 정점을 도는데엔 시간이 그리 오래 걸리지 않음
     • 순간이동하는 경우를 우선하여 방문하기 때문에 불필요한 연산이 많이 발생할 수 있는데, 방문할 수 있는 정점이 최대 10만개이기 때문에 시간 제한내에 동작할 수 있다.

고찰

• BFS는 가중치가 동일할 때만 정상동작함
• 우선순위 큐에서 연산시간이 왜이렇게 오래걸릴까라는 의문이 들어 찾아본 결과, 힙정렬 방식으로 내부에서 정렬이 일어나는걸 알게 되었다. 또한 어차피 가중치가 0인 정점만 큐의 앞쪽에 위치하면 되기 때문에 정렬이 불필요하다고 생각되어 덱을 이용하였다.

정답코드

#include <iostream>
#include <deque>
using namespace std;
#define MAX_SIZE 100001
int visit[MAX_SIZE] = { 0, };
int N, K;
struct pos {
	int cost;
	int cord;
};
int main()
{
	fill(&visit[0], &visit[MAX_SIZE - 1], -1);
	cin >> N >> K;
	if (N == K) {
		printf("%d\n", 0);
		return 0;
	}
	deque<pos> dq;
	struct pos p, np;
	p.cord = N;
	p.cost = 0;
	visit[N] = 0;
	visit[K] = -1;
	dq.push_back(p);

	while (!dq.empty()) {
		p = dq.front();
		dq.pop_front();
		if (p.cord == K) {
			printf("%d\n", visit[p.cord]);
			break;
		}
		if (p.cord * 2 < MAX_SIZE && visit[p.cord * 2] == -1 && N < K) {
			np.cost = 0;
			np.cord = p.cord * 2;
			visit[np.cord] = visit[p.cord];
			dq.push_front(np);
		}
		if (p.cord - 1 >= 0 && visit[p.cord - 1] == -1) {
			np.cost = 1;
			np.cord = p.cord - 1;
			visit[np.cord] = visit[p.cord] + 1;
			dq.push_back(np);
		}
		if (p.cord + 1 < MAX_SIZE && visit[p.cord + 1] == -1 && N < K) {
			np.cost = 1;
			np.cord = p.cord + 1;
			visit[np.cord] = visit[p.cord] + 1;
			dq.push_back(np);
		}
	}
	return 0;
}