[BFS] BOJ 13913번 숨박꼭질 4

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

13913번: 숨바꼭질 4

- 문제 파악

수빈이의 위치와 동생의 위치가 정수로 주어지고 1차원 배열에서 수빈이 위치에서 동생 위치로 가는 최소 시간과 경로를 출력하라

 

-정답

 

주의가 필요했던 점

 

1. 수빈이 위치에서 동생 위치로 가는 최소 경로 출력

   메모리 초과 발생하여 경로를 저장하는 배열을 조건문안에 넣어 최대한 메모리를 덜 차지하도록 했다.

2. 수빈이와 동생의 위치 차이가 동일할 때

    아예 BFS 시작하기 전에 처리 해버리고 프로그램을 끝내버린다.

 

#include "bits/stdc++.h"

using namespace std;


int pos[100002];
int check[100002];
int output[100002];

queue<int> q;

void func(int x, int k)
{
	int nCmp = check[x];
	if (!check[x] || check[x] == -1)
	{
		check[x] = check[k] + 1;
		q.push(x);

		if (!pos[x])
			pos[x] = k;

	}
	else
	{
		check[x] = min(check[k] + 1, check[x]);
		if (nCmp != check[x])
		{
			q.push(x);

			if (!pos[x])
				pos[x] = k;
		}
	}
}


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

	int n, m;
	cin >> n >> m;

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

	check[n] = 0;
	check[m] = -1;

	pos[n] = -1;

	q.push(n);

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

		if (k == m)
			break;
		
		int x1 = k - 1,
			x2 = k + 1,
			x3 = k * 2;

		if (x1 >= 0)		
			func(x1, k);

		if (x2 <= 100000)		
			func(x2, k);

		if (x3 <= 100000)
			func(x3, k);

	}

	cout << check[m] << "\n";

	int j = m;

	int x = 0;
	while (pos[j] != -1)
	{
		output[x++] = pos[j];
		j = pos[j];		
	}

	reverse(output, output + x);

	for (int i = 0; i < x ; i++)
		cout << output[i] << " ";

	cout << m;

}