백준 1697: 숨바꼭질

문제 요약

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

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

문제 분류

• 그래프 이론
• 그래프 탐색
• BFS

문제 풀이

BFS로 풀면 된다.

단지 if문에서 n + 1의 경우, n - 1의 경우, n * 2의 경우를 모두 탐색하며,

각각 n + 1은 k이하면 되고, n - 1은 0이상, n * 2는 최대값인 100,000이하이면 된다.

입력값의 최대가 100,000도 포함이므로 visited배열의 크기는 100,001이 되어야 한다.

또, 큐에 저장된 n은 이미 0이상, 100,000이하를 만족하므로 n - 1에서 100,000이하 인지 조건을 추가하지 않아도 된다. n + 1과 n * 2에서도 마찬가지로 각각 0이상인지의 조건을 붙이지 않아도 된다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

queue<int> q;
bool visited[100001];

int main()
{
	int n, k, level = -1, qsize;
	bool solve = false;
	cin >> n >> k;
	
	q.push(n);
	visited[n] = true;
	while (!q.empty()) {
		level++;
		qsize = q.size();
		while (qsize--) {
			n = q.front();
			q.pop();
			if (n == k) {
				solve = true;
				break;
			}
			if (n + 1 <= k) {
				if (!visited[n + 1]) {
					q.push(n + 1);
					visited[n + 1] = true;
				}
			}
			if (n - 1 >= 0) {
				if (!visited[n - 1]) {
					q.push(n - 1);
					visited[n - 1] = true;
				}
			}
			if (n * 2 < 100001) {
				if (!visited[n * 2]) {
					q.push(n * 2);
					visited[n * 2] = true;
				}
			}
		}
		if (solve) break;
	}
	printf("%d", level);
	return 0;
}