[백준] 13549: 숨바꼭질3 with Deque

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

13549번: 숨바꼭질 3

이제 알고리즘 문제풀이 방식을 조금 바꿨다.

이제는 더이상 미리 문제 유형을 보지 않고 도전하기로 했다.

그리고 엣지 케이스를 스스로 찾는 능력을 키우기 위해 질문 게시판도 자제하기로 노력하기로!

아무래도 그동안 외부의 힌트를 구한 탓인지 혼자 알고리즘을 풀 때 제대로 문제를 해결해나가지 못한 경우가 많았기 때문이다.

 

이러한 전환의 첫 시작이 된 문제, 숨바꼭질3!

다행히 난이도가 그리 높지 않기에 무난히 풀 수 있었다.

 

우선 첫 번째 요점으로 최소 시간을 구해야하기 때문에 BFS(너비 우선 탐색)을 활용하면 쉽게 풀 수 있다.

하지만 단순히 탐색한 결과를 Queue에 넣기만 하면 이 문제를 완벽하게 풀 수는 없다.

왜냐하면 규칙적으로 어떠한 행위에 대한 cost가 증가하는 것이 아니기 때문이다.

단순히 이동하는 것마다 cost가 추가되는 것이 아니라, 순간 이동을 하는 경우는 cost가 0이다. 따라서 큐의 앞 부분에 넣어줘야 한다.

그래야 최대한 0초가 걸리는 순간이동을 활용해 최소 소요 시간을 파악할 수 있다.

이러한 알고리즘에 제일 적합한 자료구조는 deque이다.

https://clay-atlas.com/us/blog/2021/09/28/cpp-en-how-to-use-deque-stl/

코드는 아래와 같다.

#include <iostream>
#include <queue>
#include <utility>
#define MAX_CNT 100000
using namespace std;
int visited[MAX_CNT] = {0};
deque<pair<int, int>> q;


int main(void){

	int a, b;
	cin >> a >> b;

	q.push_back({a, 0});

	while(!q.empty()) {
		int old = q.front().first;
		int cnt = q.front().second;
		
		q.pop_front();

		if(old == b) {
			cout << cnt << '\n';
			break;
		}

		if(old <= MAX_CNT / 2 && !visited[old * 2]) {
			visited[old * 2] = 1;
			q.push_front({old * 2, cnt});
		}

		if(old < MAX_CNT && !visited[old + 1]) {
			visited[old + 1] = 1;
			q.push_back({old + 1, cnt + 1});
		}

		if(old > 0 && !visited[old - 1]) {
			visited[old - 1] = 1;
			q.push_back({old - 1, cnt + 1});
		}
	}
}