[ 백준 13913 ] 숨바꼭질 4 (C++)

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

13913번: 숨바꼭질 4

 

숨바꼭질2 문제와 거의 비슷한데 경로까지 출력해야되는 문제다. parent 배열을 만들어 경로를 역추적 하는 것이 핵심이다. 부모를 찾는 아이디어는 합집합 찾기와 비슷하다. 

 

parent[현재 위치] = 이전 위치

// 목적지에 도달한 경우
pre1 = parent[to]
parent[pre1] = pre2

{ pre2 - pre1 - 목적지 } 경로가 성립한다

 

위 원리를 이해했다면 pre 값이 from가 같아질때까지 경로를 저장하고, 저장한 경로를 뒤집으면 구하고자 하는 답이 되는 것을 어렵지 않게 이해할 수 있다.

 

숨바꼭질2 문제는 큐에서 원소를 pop 하자마자 방문처리를 먼저 해줬었다. 그 이유는 이동 위치가 겹치는 경우를 방지하기 위함이었다. 그런데 이 문제는 그렇게 하면 parent 값 또한 겹치기 때문에 경로가 꼬이게 된다. 그리고 이 문제는 여러 가지 경로 중 한 가지만 출력하면 되므로 조건문에서 방문처리를 해주면 된다. 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define MAX 100001
using namespace std;

int map[MAX];
int parent[MAX];

int main() {

	int from, to;

	cin >> from >> to;

	queue<pair<int, int>> q;
	q.push({ from, 0 });
	int loc, time, ans;
	vector<int> route;
	map[from] = 1;

	while (!q.empty()) {
		loc = q.front().first;
		time = q.front().second;
		q.pop();

		// 목적지 도달
		if (loc == to) {
			cout << time << endl;
			while (loc != from) {
				route.push_back(loc);
				loc = parent[loc];
			}
			route.push_back(from);
			reverse(route.begin(), route.end());
			for (int elem : route)
				cout << elem << ' ';
			cout << endl;
			break;
		}

		if (loc + 1 <= MAX - 1 && !map[loc + 1]) {
			q.push({ loc + 1, time + 1 });
			map[loc + 1] = 1;
			parent[loc + 1] = loc;
		}

		if (loc - 1 >= 0 && !map[loc - 1]) {
			q.push({ loc - 1, time + 1 });
			map[loc - 1] = 1;
			parent[loc - 1] = loc;
		}

		if (loc * 2 <= MAX - 1 && !map[loc * 2]) {
			q.push({ loc * 2, time + 1 });
			map[loc * 2] = 1;
			parent[loc * 2] = loc;
		}
	}

	return 0;
}