[C/C++] 백준 13549번 - 숨바꼭질 3 (BFS)

 

 

<코드>

#include<iostream>
#include<algorithm>
#include<deque>
using namespace std;

#define MAX 100000

int N, K, x;
int check[100001];
deque<pair<int, int>> dq; // <위치, 시간>

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> K;

	dq.push_back({ N,0 });

	while (!dq.empty())
	{
		int now = dq.front().first;
		int time = dq.front().second;
		dq.pop_front();

		check[now] = true;

		if (now == K)
		{
			cout << time;
			break;
		}

		if (now - 1 >= 0 && !check[now - 1])
			dq.push_back({ now - 1,time + 1});

		if (now + 1 <= MAX && !check[now + 1])
			dq.push_back({ now + 1,time + 1 });

		if (2 * now <= MAX && !check[2 * now])
			dq.push_front({ 2 * now,time});
	}

}

 

풀이 방법

 

이번 문제는 우선순위 큐를 사용해도 되지만 덱을 쓰는 것을 좀 더 좋아하므로 덱으로 풀이를 하였다.

deque는 queue와 비슷하지만 앞뒤로 push, pop이 가능하기 때문에 순간이동의 경우에는 +-1 이동보다 우선순위가 높으므로 덱의 앞쪽에 push를 하여 우선순위를 높여주었다.

 

www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3