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

문제 링크: https://www.acmicpc.net/problem/13913

13913번: 숨바꼭질 4

1. 주의할 점

- 지나온 값들을 저장하는 Vector 구조체에 포함한다 -> 시간초과

- 지나온 값들을 저장하도록 Before배열을 사용한다

 

2. 구현

- 이전의 숨바꼭질 1,2,3와 같은 방식인 BFS로 접근한다.

- DP배열: 현재 번호까지 도달하는데 걸린 최소 시간

- Before배열: DP의 배열이 갱신되었을 때, 어떤 번호에서 현재 번호까지 왔는지 저장

- DP배열이 초기화될 때, Before배열 갱신 + 큐에 삽입을 통해 답을 도출한다.

- 경로를 구할 때, 최종 목적지에서 부터 시작해서 시작지점에 도착할때까지 경유한 번호들을 전부 Vector에 삽입후, 역순으로 출력한다.

 

#define MAX 100001
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int dp[MAX];
int before[MAX];
struct info {
	int val, idx;
};
info tmp;
int main() {
	int start, target;
	cin >> start >> target;
	for (int i = 0; i < MAX; i++) {
		dp[i] = MAX;
		before[i] = -1;
	}
	before[start] = start;
	dp[start] = 0;
	queue<info> q;
	tmp.idx = start;
	tmp.val = 0;
	q.push(tmp);
	int result = 0;
	while (!q.empty()) {
		int cidx = q.front().idx;
		int cv = q.front().val;
		q.pop();
		if (cidx == target) {
			result = cv;
			break;
		}
		if (cidx - 1 >= 0 && dp[cidx - 1] > cv + 1) {
			dp[cidx-1] = cv + 1;
			tmp.idx = cidx - 1;
			tmp.val = cv + 1;
			before[cidx - 1] = cidx;			
			q.push(tmp);
		}
		if (cidx + 1 <= MAX - 1 && dp[cidx + 1] > cv + 1) {
			dp[cidx+1] = cv + 1;
			tmp.idx = cidx + 1;
			tmp.val = cv + 1;
			before[cidx + 1] = cidx;
			q.push(tmp);
		}
		if (cidx * 2 <= MAX - 1 && dp[cidx * 2] > cv + 1) {
			dp[cidx * 2] = cv + 1;
			tmp.idx = cidx * 2;
			tmp.val = cv + 1;
			before[cidx * 2] = cidx;
			q.push(tmp);
		}
	}
	cout << result << '\n';
	int t = target;
	vector<int> ans;
	while (1) {
		ans.push_back(t);
		if (t == start) break;	
		t = before[t];
	}
	for (int i = ans.size() - 1; i >= 0; i--)
		cout << ans[i] << " ";
	system("pause");
	return 0;
}