[백준 - 1697] [BFS] 숨바꼭질

숨바꼭질 

한국어   

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

154848

44034

27588

25.032%

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

예제 입력 1 복사

5 17

예제 출력 1 복사

4

---

바킹독 알고리즘 강좌 0x09 BFS 연습문제.

해당 강좌를 참고하여 풀이함.

 

풀이 과정

기존 BFS 문제는 2차원 배열에서 상하좌우로 뻗어나가는 형식이 많았다.

이를 이용해서 1차원 배열에서 이동,순간이동 하는걸 BFS로 구현

 

 

코드

#include <iostream>
#include <queue>

#define X first
#define Y second

using namespace std;

int dist[100002]{}; 


int main()
{
	queue<int> bfsQ;
	int n = 0, k = 0; // 수빈 위치 n, 동생 위치 k

	cin >> n >> k;

	for (int i = 0; i < 100002; ++i)
		dist[i] = -1;
	dist[n] = 0; // 수빈 시작점
	bfsQ.emplace(n);
	while (!bfsQ.empty())
	{
		int cur = bfsQ.front();
		int movArr[3] = { cur - 1,cur + 1,cur * 2 };
		bfsQ.pop();
		for (int i = 0; i < 3; ++i)
		{
			int tmp = movArr[i];
			if (tmp < 0 || tmp >= 100002)
				continue;
			if (dist[tmp] != -1) // 이미 방문한 곳이라면
				continue;
			dist[tmp] = dist[cur] + 1;
			bfsQ.push(tmp);
		}
	}
	printf("%d", dist[k]);
}