[백준/BOJ] 백준 1697번 : 숨바꼭질

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

1697번: 숨바꼭질

수빈이의 위치를 start, 동생의 위치를 finish로 하여, start지점부터 finish지점까지 도달하는 가장 빠른 시간을 구한다. start지점부터 finish지점까지 bfs 하여 finish지점에 도달했을 때의 깊이가 finish지점까지 도달하는 가장 빠른 시간이다. 이 문제에서 주의해야 할 점은 start와 finish가 같을 수 도 있다는 점과, 수빈이가 움직여서 위치할 수 있는 범위가 수빈이의 위치와 동생의 위치 사이의 구간을 벗어날 수 도 있다는 점이다.

 

코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int n, k;

//start지점부터 finish지점까지 도달하는 가장 빠른 시간을 구한다
int Solve(int start, int finish)
{
	queue<int> q;
	vector<bool> discoverd(100001, false);
	vector<int> depth(100001, -1);

	//start지점과 finish지점이 같을때
	if (start == finish)
	{
		return 0;
	}

	//start지점부터 탐색을 한다
	discoverd[start] = true;
	depth[start] = 0; //start지점의 깊이는 0이다
	q.push(start);

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

		//뒤쪽으로 걷기, 앞쪽으로 걷기, 순간이동을 한다
		for (int i = 0; i < 3; i++)
		{
			int there;

			if (i == 0) //뒤쪽으로 걷기
				there = here - 1;
			else if (i == 1)//앞쪽으로 걷기
				there = here + 1;
			else //(i == 2) //순간이동
				there = here * 2;

			//해당 지점이 범위를 넘어가지 않고, 발견된적이 없다면 발견한다
			if (there >= 0 && there <= 100001 && discoverd[there] == false)
			{
				discoverd[there] = true;
				depth[there] = depth[here] + 1; //해당지점의 깊이는 here지점의 깊이+1이다
				q.push(there); //나중에 탐색할것이므로 큐에 넣는다

				//해당 지점이 finish일때
				if (there == finish)
					return depth[there]; //finish 위치까지 도달하는 가장 빠른 시간은 해당 지점의 깊이이다
			}
		}
	}

	return -1; //-1이 반환되는 부분은 일어나지 않는다
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> k;

	cout << Solve(n, k);

	return 0;
}