취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 13913번 문제인 숨바꼭질 4이다.
문제는 아래 링크를 확인하자.

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

각 숫자 N에 대하여, N+1, N-1과 2*N을 향한 (방향이 있는) 에지가 있는 방향그래프를 생각해보자.

이 그래프에서, 수빈이가 있는 점을 출발점으로, 동생이 있는 점을 도착점으로 하는 BFS를 하면 문제를 해결할 수 있다.

실제 방문순서는 이 점을 오기 전에 어떤 점에서 왔는지를 기록해두는 것(BFS트리의 부모를 기록해두는 것)으로 다시 역추적할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <stack>
#include <queue>
using namespace std;

int dist[200001];
int parent[200001];
queue<int> que;
stack<int> stk;

int cnt = 0;

void bfs() {
	while (!que.empty()) {
		int current = que.front();
		if (current > 0) {
			if (dist[current - 1] == 0) {
				dist[current - 1] = dist[current] + 1;
				parent[current - 1] = current;
				que.push(current - 1);
			}
		}
		if (current < 200000) {
			if (dist[current + 1] == 0) {
				dist[current + 1] = dist[current] + 1;
				parent[current + 1] = current;
				que.push(current + 1);
			}
		}
		if (current * 2 <= 200000) {
			if (dist[current * 2] == 0) {
				dist[current * 2] = dist[current] + 1;
				parent[current * 2] = current;
				que.push(current * 2);
			}
		}
		que.pop();
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int S, E; cin >> S >> E;
	dist[S] = 1;
	parent[S] = S;
	que.push(S);
	bfs();

	cout << dist[E] - 1 << '\n';
	
	while (E != S) {
		stk.push(E);
		E = parent[E];
	}

	cout << S << ' ';
	while (!stk.empty()) {
		cout << stk.top() << ' ';
		stk.pop();
	}
}