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

문제 링크

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

 

문제 정보

입력

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

출력

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

 

풀이

 이 문제는 BFS의 응용 문제로 1차원에서의 BFS를 돌리는 문제이다. 

 

소스 코드

#include <bits/stdc++.h>
using namespace std;

#define X first
#define Y second

int dist[100002];
int n, k;

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> k;
	fill(dist, dist + 100002, -1);
	
	queue<int> Q;
	Q.push(n);
	dist[n] = 0;
	
	while (!Q.empty()) {
		auto cur = Q.front();
		Q.pop();
		
		for (int nxt : {cur -1, cur + 1, 2 * cur}) {
			if (nxt < 0 || nxt >= 100002) {
				continue;
			}
			if (dist[nxt] != -1) {
				continue;
			}
			
			dist[nxt] = dist[cur] + 1;
			Q.push(nxt);
		}
	}
	
	cout << dist[k];
	
	return 0;
}