[백준] 알고리즘 13549번 - 숨바꼭질 3문제

문제

https://www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

소스코드

#include <iostream>
#include <limits.h>
#include <vector>
#include <queue>
#include <algorithm>
#include<memory.h>
#include <stdio.h>
using namespace std;
int n, k;
bool check[100001];
int dist[100001];
deque<int> dq;
void bfs(int x) {
	dq.push_back(x);
	while (!dq.empty()) {
		int ox = dq.front();
		dq.pop_front();
		if (ox == k) return;
		if (ox * 2 <= 100001 && !check[ox*2]) {
			dq.push_front(ox*2);
			check[ox * 2] = true;
			dist[ox * 2] = dist[ox];
		}
		if (ox + 1 <= 100001 && !check[ox+1]) {
			dq.push_back(ox + 1);
			check[ox + 1] = true;
			dist[ox + 1] = dist[ox] + 1;
		}
		if (ox - 1 >= 0 && !check[ox-1]) {
			dq.push_back(ox - 1);
			check[ox - 1] = true;
			dist[ox - 1] = dist[ox] + 1;
		}
	}
}
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	cin >> n >> k;
	bfs(n);
	cout << dist[k];
}

해설

BFS를 큐를 이용해서 구현하려면 가중치가 같아야 한다고 했습니다. 구하려는 값과 가중치가 일치해야 문제를 풀 수 있는데요, 이 문제는 순간이동을 하게되면 가중치가0이고 나머지 두개의 경우에는 가중치가 1입니다.

우리는 K시간에 최소의 시간대로 도착해야하므로, 우선순위가 순간이동인 0초부터 무조건 먼저 계산을 해줘야한다. 그러므로 큐를 두개사용하거나 덱을 사용하는건데 여기서는 덱을 사용해보겠습니다.

기존 bfs와 틀은 비슷하지만, 우선순위에 따라 0초가 걸리는 순간이동은 앞부분에 넣어주고 1초가 걸리는 나머지 연산들은 뒤에 넣어줌으로써 우선순위를 보이지않는 경계에 미묘하게 넣는것을 볼 수 있습니다.

이렇게하면, 무조건 0초인 시간대인 부분을 먼저 탐색하기에 이후에 0초시간대에 한번 방문하려해도 이미 방문했으므로 방문하지 않게되므로 우선순위에 따라 시간을 분배하여 방문한다고 볼 수 있습니다.