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

시험기간엔 PS가 재밌어진다 ㅎ 

 

숨바꼭질 1,2,3에 이은 4번째이다. bfs라는 풀이법은 변하지 않았지만 조금 씩 세부적인 사항을 요구한다. 이번에는 지나온 경로에 관해 출력해야한다.

지나온 경로를 출력하는 것에 가장 좋은 방법은 dfs이지만 이 문제에는 "최단거리" 이기 때문에 dfs를 선택하면 무조건 시간초과가 뜬다. 

때문에 bfs에서 함수를 더해 경로를 저장해야한다.

그 방법은 배열을 만들고 그 배열에 이전 정보를 저장해놓는 것이다. DP와 비슷하다고 보면 된다. 

 

#include<iostream>
#include<vector>
#include<algorithm>
#include <queue>
using namespace std;
queue<pair<int, int>> Q;
int currentnumber[100001] = {0,};
int n, m;

bool visited[100001] = { false, };

void bfs() {
	while (!Q.empty()) {
		int cnt = Q.front().first;
		int here = Q.front().second;
		Q.pop();
		if (here == m) {
			vector<int> result;
			cout << cnt << '\n';
			int index = here;
			for(int i = 0; i < cnt; i++) {
				int tmp = currentnumber[index];
				index = tmp;
				result.push_back(tmp);
			}
			for (int i = cnt - 1; i > -1; i--) {
				cout << result[i] << " ";
			}
			cout << m;
			exit(0);
		}

		int nextX;

		nextX = here + 1;
		if (nextX < 100001 && visited[nextX] == false) {
			Q.push(make_pair(cnt + 1, nextX));
			currentnumber[nextX] = here;
			visited[nextX] = true;
		}

		nextX = here - 1;
		if (nextX > -1 && visited[nextX] == false) {
			Q.push(make_pair(cnt + 1, nextX));
			currentnumber[nextX] = here;
			visited[nextX] = true;
		}

		nextX = here * 2;
		if (nextX < 100001 && visited[nextX] == false) {
			Q.push(make_pair(cnt + 1, nextX));
			currentnumber[nextX] = here;
			visited[nextX] = true;
		}
	}
}

int main() {
	cin >> n >> m;
	Q.push(make_pair(0, n));
	bfs();
}