[백준 C++] 1679 : 숨바꼭질

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

이전글에 풀었던 미로 탐색에서 사용하였던 방법을 응용하면 되는 문제이다.

---

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

vector<int> list;
vector<bool> visited;
vector<int> answer;

void bfs(int start)
{
	int size = list.size();
	queue<int> que;
	que.push(start);

	visited[start] = true;

	while (!que.empty())
	{
		int current = que.front();
		que.pop();

		if (current - 1 >= 0)
		{
			if (!visited[current - 1])
			{
				que.push(current - 1);
				visited[current - 1] = true;

				answer[current - 1] = answer[current] + 1;
			}
		}
		if (current + 1 < size)
		{
			if (!visited[current + 1])
			{
				que.push(current + 1);
				visited[current + 1] = true;

				answer[current + 1] = answer[current] + 1;
			}
		}
		if (current * 2 < size)
		{
			if (!visited[current * 2])
			{
				que.push(current * 2);
				visited[current * 2] = true;

				answer[current * 2] = answer[current] + 1;
			}
		}
	}
}

int main()
{
	int N, K;
	cin >> N >> K;

	list = vector<int>(((N > K ? N : K) + 1) * 2, 0);
	visited = vector<bool>(((N > K ? N : K) + 1) * 2, false);
	answer = vector<int>(((N > K ? N : K) + 1) * 2, 0);

	bfs(N);

	cout << answer[K] << '\n';

	return 0;
}

더 정확하게 계산하면 배열의 크기가 줄어들 수 있겠지만, 간단하게 N과 K중 큰 수 이전에 * 2를 할 수 있다고 생각하여 배열의 크기를 ((N > K ? N : K) + 1) * 2 로 설정하였다.

한번 방문한 곳은 이전 방문한 곳의 개수에 +1로 해주어 answer에 저장하는 방식으로 구현하였다.