[백준] 알고리즘 13913번 - 숨바꼭질4문제

문제

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

13913번: 숨바꼭질 4

소스코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include<memory.h>
#include <stdio.h>
using namespace std;
const int MAX = 200000;
int n, k;
int dist[MAX + 1];
int from[MAX + 1];
queue<int> qu;
void go(int p) {
	if (p == n) {
		cout << p << " ";
		return;
	}
	go(from[p]);
	cout << p << " ";
}
void bfs(int x) {
	qu.push(x);
	dist[x] = 1;
	while (!qu.empty()) {
		int ox = qu.front();
		qu.pop();
		if (ox + 1 <= MAX) {
			int nx = ox + 1;
			if (dist[nx]==0) {
				dist[nx] = dist[ox] + 1;
				from[nx] = ox;
				qu.push(nx);
			}
		}
		if (ox - 1 >= 0) {
			int nx = ox - 1;
			if (dist[nx]==0) {
				dist[nx] = dist[ox] + 1;
				from[nx] = ox;
				qu.push(nx);
			}
		}
		if (ox * 2 <= MAX) {
			int nx = ox * 2;
			if (dist[nx]==0) {
				dist[nx] = dist[ox] + 1;
				from[nx] = ox;
				qu.push(nx);
			}
		}
	}
}
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	cin >> n >> k;
	bfs(n);
	cout << dist[k]-1<<"\n";
	go(k);
}

해설

숨바꼭질 문제와 같은 문제이지만, 이 문제에서는 이동하는 방법도 출력해야 한다.

다이나믹 문제의 LIS 14002번문제에서 역추적하는 것을 해보았다.

대부분의 모든 문제가 알고리즘이 달라도 역추적하는 것은 N -> K로간다 친다면 K는 어디에서 와서 최단거리를 계산했는지를 저장해줘야 한다.

그렇다면 우리는 from이라는 배열을 생성하여 nx에 ox를 저장시켜준다면 bfs는 모든 경로를 다 탐색하기에 시작점까지 저장할 수 있을 것이다.

역추적에 관한 설명은 좀 더 추가할 예정이다.