[백준 13549] C++ 숨바꼭질 3

1. 문제

---

순간이동을 왜 0초에 하는 것일까?

2. 문제 분석

---

가장 많은 사람들이 헤메는 부분이 바로

순간이동의 시간이 0초인 부분이다.

 

이 조건 하나로, 수빈이의 걷기보다 순간이동이 더 우선순위를 가지게 된다.

 

---

BFS는 edge간의 가중치가 없고, 무방향 그래프일 경우 최단거리를 찾게 해준다.

다익스트라는 edge간의 가중치가 있을 경우 최단거리를 찾게 해준다.

---

 

이 문제는 edge에 해당하는 {뒤로 걷기, 앞으로 걷기, 순간 이동}의 가중치가 서로 다르다.

따라서, 다익스트라 알고리즘을 사용한다.

 

3. 풀이

---

여러 풀이 방식이 있으나, deque를 사용하여 풀이해보자.

선입선출(FIFO)의 queue와, 후입선출(LIFO)의 stack의 기능을 모두 갖춘 deque로

앞과 뒷 방향에서 push를 하고, 매번 front의 값을 pop하여 연산해나간다.

 

다음 풀이 방식은 아래 블로그의 것을 참고하였다.

https://jdselectron.tistory.com/58

[백준 13549, c++] 숨바꼭질3(bfs, deque, priority_queue)

• 순간 이동을 할 경우 해당 좌표는 덱의 앞에 넣는다.
• 걷는 이동을 할 경우 해당 좌표는 덱의 뒤에 넣는다.
• 좌표를 덱에서 꺼낼 때, 덱의 앞에서부터 꺼내오는 pop_front()를 사용하므로 순간이동의 우선순위를 높게 처리할 수 있다.

4. 코드

---

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

#define MAX_SIZE 100000+1

deque<int> DQ;
int visited[MAX_SIZE];

priority_queue<int, vector<int>, greater<int>> PQ;
int main()
{
	ios_base::sync_with_stdio(false);
	int n, k;
	cin >> n >> k;

	memset(visited, 0, sizeof(int) * MAX_SIZE);

	DQ.push_back(n);
	visited[n] = 1;	

	if (n >= k)
		PQ.push(n - k);
	else
	{
		// 순간이동이 0초 이므로, 가중치가 있는 bfs => 다익스트라 => deque or priority queue
		while (!DQ.empty())
		{			
			int num = DQ.front();
			DQ.pop_front();			

			if (num == k)
			{				
				PQ.emplace(visited[num] - 1);
				continue;
			}
			
			// 순간이동은 우선순위에서 앞이니 push_front
			if (num * 2 < MAX_SIZE && !visited[num * 2])
			{
				DQ.push_front(num * 2);
				visited[num * 2] = visited[num];
			}

			// 걷는건 우선순위에서 밀리므로 push_back			

			if (num - 1 > 0 && !visited[num - 1])
			{
				DQ.push_back(num - 1);
				visited[num - 1] = visited[num] + 1;
			}

			if (num + 1 < MAX_SIZE && !visited[num + 1])
			{
				DQ.push_back(num + 1);
				visited[num + 1] = visited[num] + 1;
			}
		}
	}

	std::cout << PQ.top();
}