[백준/C++] 숨바꼭질

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 N에서 출발해 M에 도착하는데 걸리는 가장 적게 걸리는 시간을 구하는 문제다.

그러므로 BFS로 풀면 M에 처음 도달한 순간이 가장 시간이 적게 걸린 것이다.

 

임의의 점 X에서 다음에 갈 수 있는 곳은 X+1, X-1, X*2이다. 그러므로 이 3곳에 대해 queue에 삽입해 탐색을 하면 된다.

여기서 다음에 갈 위치가 이미 방문한 적이 있다면, queue에 삽입할 필요가 없다.

 

왜냐하면 BFS로 탐색을 하기 때문에 첫 방문이 가장 시간이 적게 걸린 순간이기 때문이다.

 

이제 문제를 풀 때, 방문을 체크할 visited vector와 queue를 이용해 문제를 풀면 된다,

 

 

​

[아이디어 정리]

1. N에서 M에 도착하는데 가장 적게 걸리는 시간을 구하는 문제이므로, BFS로 탐색해 M에 첫 방문했을 때 시간을 구하면 된다.
2. 특정 위치 X에서 갈 수 있는 곳은 X+1, X-1, X*2 이므로 3곳의 위치를 이전에 방문했는지 확인하고 방문하지 않았다면 queue에 넣는다.
3. M에 방문했다면, 그 때 걸린 시간을 출력하고 함수를 종료한다.

 

 

 

Code

 

 

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

int main()
{
	int N , M;
	cin >> N >> M;
	vector<int> visited(100001, false);
	queue<pair<int, int>> q;//위치, 시간
	pair<int, int> np=make_pair(N,0);
	visited[N] = true;
	if (N == M) {
		cout << 0;
		return 0;
	}
	q.push(np);
	int nv;
	while(true)
	{

		np = q.front();
		q.pop();
		for (int i : { -1, 1})
		{
			nv = np.first + i;
			if (nv >= 0 && nv <= 100000 && !visited[nv])
			{
				visited[nv] = true;
				if (nv == M) 
				{
					cout << np.second + 1;
					return 0;
				}
				q.push(make_pair(nv, np.second + 1));
			}
		}
		nv = np.first * 2;
		if (nv >= 0 && nv <= 100000 && !visited[nv])
		{
			visited[nv] = true;
			q.push(make_pair(nv, np.second + 1));
			if (nv == M)
			{
				cout << np.second + 1;
				break;
			}
		}
	}
	return 0;
}

 

---

2차원 평면이 아니라 처음 보면 헷갈릴 수 있지만, 2차원 평면에서 상하좌우로 이동하는 것과 똑같은 BFS문제다 EZ

 

1697번: 숨바꼭질