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

www.acmicpc.net/problem/13913

13913번: 숨바꼭질 4

기존 숨바꼭질 문제에 최소 시간이 걸리는 경로의 기록까지 구해야하는 문제입니다. 경로를 기록하기 위해서 배열 record를 선언하였고, 큐가 진행될때 마다 다음 위치에 이전 위치가 기록됩니다. 수빈이가 동생을 만나면, traceBack()  함수를 통해 현재 수빈의 위치에서 부터 처음 위치까지 역으로 추적하도록 구현했습니다.

 

#include <iostream>
#include <queue>
#include <deque>
#include <cstring>
#define MAX 200001
using namespace std;

int n, k;
int visit[MAX];
int record[MAX]; // 경로를 기록할 배열

// 최소 시간 추적
void traceBack() {
	deque<int> dq; // 역으로 추적한 값을 앞부터 넣어야하므로 덱을 사용
	int prev = k; 
	while(prev != n) {
		dq.push_front(prev);
		prev = record[prev];
	}
	dq.push_front(n);
	for(int i = 0; i < dq.size(); i++) {
		cout<<dq[i]<<" ";
	}
	
}

void BFS() {
	memset(visit, -1, sizeof(visit));
	queue<int> q;
	q.push(n);
	visit[n] = 0;
	while(!q.empty()) {
		int now = q.front();
		q.pop();
		if(now == k) {
			cout<<visit[k]<<"\n";
			traceBack();
			break;
		}
		if(now * 2 <= 100000 && visit[now * 2] == -1) {
			q.push(now * 2);
			visit[now * 2] = visit[now] + 1;
			record[now * 2] = now;
		}
		if(now -1 >= 0 && visit[now - 1] == -1) {
			q.push(now - 1);
			visit[now - 1] = visit[now] + 1;
			record[now - 1] = now;
		}
		if(now + 1 <= 100000 && visit[now + 1] == -1) {
			q.push(now + 1);
			visit[now + 1] = visit[now] + 1;
			record[now + 1] = now;
		}
	}
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>k;
	BFS();
}