백준 1697 : 숨바꼭질

1. 문제 : https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

 

2. 문제 접근

• 주어진 규칙에 따라 이동하므로 정해진 경우의 수가 존재. -> 탐색
• 각 위치를 노드로 표현했을 때 A라는 지점으로 다시 돌아올 수 있음. -> 순회가 존재 -> 그래프
• 그래프를 탐색할 때 가장 빠른 시간을 구해야하므로 Depth가 가장 짧은 경로를 구해야 함. -> BFS
• 이미 방문한 노드라면 BFS로 탐색하기 때문에 이전에 방문한 경로가 가장 짧은 경로임. -> 백트레킹

 

3. 문제 해결

1. 시작점 $N$부터 BFS 탐색 (Queue로 구현)
2. 이동할 수 있는 세 가지 방법에 대해 조건 검사 $( X + 1,  2 * X, X- 1)$
   • 이동할 위치가 범위 내에 있는가? (0 ~ 100,000)
   • 이미 방문한 노드가 아니여야 함.
3. 이동한 위치가 $K$라면 해당 Depth를 반환

 

4. 코드

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

using namespace std;

int solution(int N, int K)
{
	const int MAX = 100000;

	int answer = 0;
	queue<pair<int, int>> bfs;
	vector<bool> visited;

	// Initialize the value { level, position }
	bfs.push({ 0, N });
	for (int i = 0; i <= MAX; i++)
	{
		visited.push_back(false);
	}

	// Search the position by bfs
	while (!bfs.empty())
	{
		pair<int, int> move = bfs.front();
		bfs.pop();

		// Find the position
		if (move.second == K)
		{
			answer = move.first;
			break;
		}
		else
		{
			if (move.second + 1 <= MAX && !visited[move.second + 1])
			{
				bfs.push({ move.first + 1, move.second + 1 });
				visited[move.second + 1] = 1;
			}
			if (move.second * 2 <= MAX && !visited[move.second * 2])
			{
				bfs.push({ move.first + 1, move.second * 2 });
				visited[move.second * 2] = 1;
			}
			if (move.second - 1 >= 0 && !visited[move.second - 1])
			{
				bfs.push({ move.first + 1, move.second - 1 });
				visited[move.second - 1] = 1;
			}
		}
	}
	
	return answer;
}

int main()
{
	int N, K;

	cin >> N >> K;

	cout << solution(N, K);

	return 0;
}