[bfs 최단거리] 숨바꼭질4 13913

숨바꼭질4 13913

 

풀이코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
// 13913 숨바꼭질 4
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];
	int parent[MAX + 1];
	fill_n(distance, MAX + 1, -1);
	fill_n(parent, MAX + 1, -1);
	queue<int> q;
	
	cin >> start >> end;
	
	distance[start] = 0;
	parent[start] = start;
	q.push(start);
	
	bool ok = true;

	while(ok){
		int currentNode = q.front();
		q.pop();
		
		int nextNodes[3] = {currentNode - 1, currentNode + 1, currentNode * 2};
		
		for(int nextNode : nextNodes){
			if(nextNode > MAX || nextNode < 0) continue;
			if(distance[nextNode] == -1){
				q.push(nextNode);
				distance[nextNode] = distance[currentNode] + 1;
				parent[nextNode] = currentNode;
			}
			if(nextNode == end) ok = false;
		}
	}
	cout << distance[end] << '\n';
	
	int currentNode = end;
	vector<int> ans;
	while(true){
		ans.push_back(currentNode);
		if(currentNode == start) break;
		int nextNode = parent[currentNode];
		currentNode = nextNode;
	}
	for(int i = ans.size() - 1; i >= 0; i--) cout << ans[i] << ' ';
	cout << endl;
	
}

 

해설

---

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

풀이

1. 기존 문제 에다가 parent 라는 배열만을 추가한다.

- distance[다음] = distance[이전] + 1 이므로, parent[다음] = 현재 노드 라고 정의한다.

- 그러면, 끝점에서 처음까지 어떤 경로로 최솟값을 만들었는지 역추적할 수 있다.

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