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

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

13913번: 숨바꼭질 4

https://www.acmicpc.net/problem/1697 문제와 똑같이 풀면 되는데 방문했던 경로를 출력해야 하는 문제이다.

1차원 배열에 대해 BFS를 수행한다고 생각하고, -1일때, +1일때, *2일때를 조건문으로 조사하면 된다.

 

내가 생각한 방법은 다음과 같다.

1. 먼저 -1, +1, *2에 대해 BFS를 수행해서 최단거리가 몇초인지 구한다. (*0 이하일때 -1 하지 않기, 10만 이상일때 *2 하지 않기등 예외처리 하기, 시작점은 0초임을 주의하기)

2. 이후 동생의 점을 시작점으로 하여 수빈이의 점에 도착할 때 까지 BFS 수행하고, 이때의 경로는 저장해두기

3. 2에서 저장한 경로 뒤집기(동생 -> 수빈의 경로이기 때문에 반대로 뒤집어야 수빈이 -> 동생 경로가 된다)

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX 200010
int n, k;
int board[MAX];
int dist[MAX];
bool vis[MAX];
queue <int> q;
vector <int> v;
void input()
{
	cin >> n >> k;
}
int solve()
{
	q.push(n);
	vis[n] = true;
	int res = 0;
	while(!q.empty())
	{
		int cur = q.front(); q.pop();
		if (cur == k)
		{
			res = dist[cur]; break;
		}
		if (cur > 0 && !vis[cur - 1])
		{
			q.push(cur - 1);
			vis[cur - 1] = true;
			dist[cur - 1] = dist[cur] + 1;
		}
		if (cur < MAX && !vis[cur + 1])
		{
			q.push(cur + 1);
			vis[cur + 1] = true;
			dist[cur + 1] = dist[cur] + 1;

		}
		if ((cur < 100000) && !vis[cur * 2])
		{
			q.push(cur * 2);
			vis[cur * 2] = true;
			dist[cur * 2] = dist[cur] + 1;
		}
	}

	while (!q.empty()) q.pop();
	v.push_back(k);
	int t = res - 1;
	q.push(k);
	while (!q.empty())
	{
		int cur = q.front(); q.pop();
		if (cur == n) 
			
			break;
		if (dist[cur + 1] == t && vis[cur+1])
		{
			q.push(cur + 1);
			v.push_back(cur + 1);
		}
		else if (dist[cur - 1] == t && vis[cur-1])
		{
			q.push(cur - 1);
			v.push_back(cur - 1);
		}
		else 
		{
			q.push(cur / 2);
			v.push_back(cur / 2);
		}
		t--;
	}
	reverse(v.begin(), v.end());
	return res;
}
int main()
{
	cin.tie(0); ios::sync_with_stdio(0);
	input(); cout << solve() << "\n";
	for (auto i : v)
		cout << i << ' ';
}