[백준] 숨바꼭질 (1697번)

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 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

힌트

수빈이가 5-10-9-18-17 순으로 가면 4초만에 동생을 찾을 수 있다.

---

아주 쉬운 bfs의 기본격인 문제이다.

i까지의 최소 거리를 뜻하는 배열 p를 최대값 987654321로 초기화한다. 처음 시작지점 p[N]은 0을 저장한 후 int형 queue에 값을 넣는다.

while문에선 q가 빌때까지 같은 일을 반복한다. 일단 queue에 제일 앞에 있는 값을 꺼내서 K와 같으면 종료하고 아니라면 x+1, x-1, 2x가 모두 범위 내에 있고 방문한적이 없거나 거리가 더 먼 경우 거리를 지금거리+1로 변경한 후 queue에 넣는다. 

 

중간에 if 조건문 세개가 있는 부분을 for문으로 반복해서 구현할 수도 있는 걸 구글링하다 발견했다.

방법은 이렇게 쓰면된다. for (int nx : {x-1, x+1, 2*x}) 

이 방법이 더 간편한 것 같다.

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/%EC%88%A8%EB%B0%94%EA%BC%AD%EC%A7%88(1697%EB%B2%88).cpp 

chosh95/STUDY

C++ 코드

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int N, K;
int p[100001];
	
void bfs(int n)
{
	queue<int> q;
	q.push(N);
	while (!q.empty()) {
		int x = q.front();
		if (x == K) return;
		q.pop();
		if (x - 1 >= 0 && p[x - 1] > p[x] + 1) {
			p[x - 1] = p[x] + 1;
			q.push(x - 1);
		}
		if (x + 1 <= 100000 && p[x+1] > p[x] + 1) {
			q.push(x + 1);
			p[x + 1] = p[x] + 1;
		}
		if (x * 2 <= 100000 && p[x*2] > p[x] + 1) {
			q.push(x * 2);
			p[2 * x] = p[x] + 1;
		}
	}
}
int main()
{
	cin >> N >> K;
	for (int i = 0; i <= 100000; i++) p[i] = 987654321;
	p[N] = 0;
	bfs(N);
	cout << p[K] << endl;
}