[백준] 13913번 숨바꼭질 4

링크

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

13913번: 숨바꼭질 4

풀이

 

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 문제이다.

 

숨바꼭질 1에서 가장 빠르게 갈 수 있는 경로를 출력하는 것이 추가되었다.

 

처음에는 문제를 풀 때 각 위치마다 vector를 만들어서 여태까지 온 위치를 모조리 추가해주었는데 바로 여지없이 메모리 초과가 났다.

 

그래서 생각난 게 내가 다음에 도착한 위치에 내가 어디서 왔는지를 저장해두면 어떨까 라는 생각을 하게 되었다.

 

어차피 BFS로 탐색을 하기 때문에 방문하지 않은 곳을 처음에 도착하면 무조건 최소 시간에 도착 함을 알 수 있기 때문에 새로 도착한 지점에 이전에 있었던 자리를 저장하도록 하였다.

 

모두 저장한 후에 동생이 있던 자리에서 역순으로 수빈이가 원래 있던 자리까지 찾아가며 vector에 다시 경로를 추가해주었고 

 

추가된 경로를 역순으로 출력해주면 된다.

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<set>
#include<map>
#include<cstring>
#include<cmath>

#define SIZE 100010
const int INF = 2e9;
using namespace std;

typedef long long int ll;

//움직인 횟수 , 위치에 도착 할수 있는 경우의 수
pair<int,int> v[SIZE];
queue<int> q;

int move(int here, int d) {
	if (d == 0) {
		return here-1;
	}
	else if (d == 1) {
		return here+1;
	}
	else if (d == 2) {
		return here * 2;
	}
}

void init() {
	for (int i = 0; i < SIZE; i++) {
		v[i].first = INF;
		v[i].second = 0;
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	init();
	int N, K; cin >> N >> K;

	if (N == K) {
		cout << 0 <<"\n"<< N;
		return 0;
	}

	q.push(N);
	v[N].first = 0;

	while (!q.empty()) {
		int h = q.front(); q.pop();
		
		for (int d = 0; d < 3; d++) {
			int n = move(h, d);

			//수빈이의 다음 위치
			if (n < 0 || n > 100000)
				continue;

			//처음에 도착 했다면 
			if (v[n].first > v[h].first + 1) {
				q.push(n);
				v[n].first = v[h].first + 1;
				v[n].second = h;

			}
		}

	}

	int index = K;
	vector<int> res;
	res.push_back(index);

	//동생 위치에서 수빈이가 원래 있던 자리까지 탐색
	while (1) {
		int previous = v[index].second;
		res.push_back(previous);
		if (previous == N)
			break;
		index = previous;
	}
	cout << v[K].first << "\n";

	//경로 역순으로 출력
	for (auto it = res.rbegin(); it != res.rend(); it++) {
		cout << *it << " ";
	}
	
	return 0;
}