[deque] 13549 숨바꼭질3

13549 숨바꼭질 3

 

풀이코드 (deque 사용)

#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
using namespace std;
// 13549 숨바꼭질3

const int MAX = 100000;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); 
	cout.tie(nullptr); 

	int start, end;
	int distance[MAX + 1];
	fill_n(distance, MAX + 1, -1);
	deque<int> deq;
	
	cin >> start >> end;
	
	distance[start] = 0;
	deq.push_front(start);
	
	bool ok = true;

	while(ok){
		int currentNode = deq.front();
		deq.pop_front();
		
		int nextNodes[3] = {currentNode - 1, currentNode + 1, currentNode * 2};
		
		for(int nextNode : nextNodes){
			if(nextNode > MAX || nextNode < 0) continue;
			if(distance[nextNode] == -1){
				// 가중치가 0인, 2배 순간이동은 덱의 앞에 푸시
				if(nextNode == currentNode * 2){
					deq.push_front(nextNode);
					distance[nextNode] = distance[currentNode];
				}
				// 가중치가 1인, -1 혹은 +1 은 덱의 뒤에 푸시
				else{
					deq.push_back(nextNode);
					distance[nextNode] = distance[currentNode] + 1;
				}
			}
			if(nextNode == end) ok = false;
		}
	}
	cout << distance[end] << '\n';
	
}

풀이코드 (que 2개_강의 코드)

#include <iostream>
#include <queue>
#include <deque>
using namespace std;
bool c[1000000];
int d[1000000];
int MAX = 1000000;
int main() {
 int n, m;
 cin >> n >> m;
 c[n] = true;
 d[n] = 0;
 deque<int> q;
 q.push_back(n);
 while (!q.empty()) {
 int now = q.front();
 q.pop_front();
 if (now*2 < MAX) {
 if (c[now*2] == false) {
 q.push_front(now*2);
 c[now*2] = true;
 d[now*2] = d[now];
 }
 }
 if (now-1 >= 0) {
 if (c[now-1] == false) {
 q.push_back(now-1);
 c[now-1] = true;
 d[now-1] = d[now] + 1;
 }
 }
 if (now+1 < MAX) {
 if (c[now+1] == false) {
 q.push_back(now+1);
 c[now+1] = true;
 d[now+1] = d[now] + 1;
 }
 }
 }
 cout << d[m] << '\n';
 return 0;
}

해설

---

적용한 레시피 / 방법론 + 접근법

 

풀이

1. 가중치가 0 혹은 1이다. 일반적인 BFS 로는 할 수 없다.

1-1. 현재 큐와 다음 큐 즉, 큐 2개를 이용하여 BFS 를 진행한다.

1-2. 덱을 사용하여 BFS 를 진행한다.

1-2-ㄱ. 가중치가 0이면 덱의 앞에 삽입. 가중치가 1이면 덱의 뒤에 삽입.

1-2-ㄴ. 덱의 앞에 삽입했다는 말은, 기존의 BFS 관점에서 보았을 때, 다시 반복문이 돌며 덱의 앞에 삽입한 것의 인접 정점들을 다시 순회한다는 것이다. 

- BFS 로 최소 비용을 구하는 원리는, BFS 가 단계별로 진행된다는 점 을 이용하는 것이었다. 비용이 0일 때, 1일 때, 2일 때.. 등 단계가 확실하게 나누어져있었다. 가중치가 1일 때는 인접 리스트들을 큐에 push 하며 이것을 구현했다. 

그렇다면, 이 문제는 무엇이 달랐는가. 가중치가 0인 것이 등장했다. 가중치가 0이라는 것은 그것을 실행해도 비용 단계가 늘어나지 않는다는 뜻이다. 그러므로, 가중치가 0인 것은 단계가 늘어나지 않았기에 덱의 왼쪽에 push 해주고, 가중치가 1인 것은 기존의 문제와 같게 오른쪽에 push 해준 것이다.

아쉬웠던 부분 / 오답 원인 / 개선해야 할 점