백준 13913 c++ 숨바꼭질 4

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

13913번: 숨바꼭질 4

---

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

둘째 줄에 어떻게 이동해야 하는지 공백으로 구분해 출력한다.

---

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
using namespace std;
int N;
int K;
bool visit[100001];
int map[100001];
stack<int> result;
vector<vector<int>> pre(100001); //본인의 이전 부모노드를 저장하는 벡터

void bfs()
{
	queue<int> q;
	q.push(N);
	map[N] = 0;
	while (!q.empty())
	{
		if (visit[K])
			break;
		int now = q.front();
		q.pop();
		int dx[3] = { 1,-1,now };
		if (now == 0)//특이 케이스 0에서 시작할 때
		{
			now = 1;
			visit[1] = true;
			map[1] = 1;
			pre[1].push_back(0);
			q.push(1);
		}
		else
		{
			for (int i = 0; i < 3; i++)
			{
				int nx = now + dx[i];
				if (nx > 100001)
					continue;
				else
				{
					if (visit[nx])
						continue;
					q.push(nx);
					map[nx] = map[now] + 1;
					pre[nx].push_back(now);
					visit[nx] = true;
				}
			}
		}
	}
	return;
}

int main()
{
	cin >> N >> K;
	if (N == K)//특이케이스 N 과 K가 같을 때
		cout << 0 << '\n' << N;
	else
	{
		bfs();
		cout << map[K] << '\n';
		//순서 구하기
		int PosBro = K;
		for (int i = 0; i <= map[PosBro]; i++)
		{
        //이전 부모노드를 result queue에 저장한다
			int temp = K;
			result.push(temp);
			if (!pre[temp].empty())
			{
				K = pre[temp].front();
			}
		}
        //result queue에 저장된 순서 전부 출력
		while (!result.empty())
		{
			cout << result.top() << ' ';
			result.pop();
		}
	}

}

---

pre 2차원배열을 추가하여 자식노드 이전의 부모노드를 저장하였고

부모노드들을 result queue에 저장하여 출력하도록 하였다.

그 외 기본적인 bfs알고리즘은 다음 문제를 따랐다.

https://mun-coding.tistory.com/132

백준 1697 c++ 숨바꼭질