숨바꼭질4 13913

숨바꼭질4 13913

숨바꼭질4 13913

풀이코드

#include #include #include #include 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 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] << '

'; int currentNode = end; vector 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[다음] = 현재 노드 라고 정의한다.

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

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

from http://private-k.tistory.com/142 by ccl(A) rewrite - 2021-10-03 12:00:15