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

 

 

<코드>

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

#define MAX 100000

int N, K, pos;
int time[100001][2]; //(시간, 이전 위치)
queue<int> q;
vector<int> v;

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

	cin >> N >> K;

	q.push(N);

	while (!q.empty())
	{
		int now = q.front();
		q.pop();

		if (now == K) break;

		for (int next : {now-1,now+1,2*now})
		{
			if (next == N) continue; // 출발위치는 제외.

			if (next >= 0 && next <= MAX && !time[next][0])
			{
				time[next][0] = time[now][0] + 1;
				time[next][1] = now;
				q.push(next);
			}
		}

	}
	cout << time[K][0] << '\n';

	v.push_back(K);
	pos = K;
	while (true)
	{
		if (pos == N) break;
		v.push_back(time[pos][1]);
		pos = time[pos][1];
	}

	while (!v.empty())
	{
		cout << v.back() << " ";
		v.pop_back();
	}
}

 

풀이 방법

 

<배열 정의>

time[x][0] : 위치 x에 도달하는데 걸린 최소 시간.

time[x][1] : 위치 x 이전의 위치 (만약 time[17][1] = 16 이라면 '17'로 이동하기 전 위치는 '16'이였다는 의미)

 

 

 

www.acmicpc.net/problem/13913

13913번: 숨바꼭질 4