(C++)[백준 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

 

수빈이의 위치가 N이고 동생이 K일때, 수빈이가 매 초마다 N+1, N-1, N*2로 이동할 수 있으면 몇 초 뒤에 K에 도착하는가를 묻는 문제이다. BFS 문제이고, 어려운 부분은 크게 없었다.

 

나는 다음과 같은 로직으로 풀었다.

1. N or N-1 or N+1 or N*2가 K일때까지 N-1, N+1, N*2를 큐에 넣고 BFS (이때, 증가하는 매 초를 배열 board에 저장)

2. 만약 K라면 현재 cur 배열의 값 + 1을 리턴 (0초부터 시작했기 때문)

#include <iostream>
#include <queue>
using namespace std;
#define MAX 200005
#define INF 987654321
queue <int> q;
int board[MAX];
int n, k;
void input()
{
	cin >> n >> k;
	fill(board, board + MAX, INF);
	board[n] = 0;
	board[k] = -1;
	q.push(n);
}
int solve()
{
	while (!q.empty())
	{
		int cur = q.front(); q.pop();
        // 로직 2번 부분
		if (cur == k || cur-1 == k || cur+1 == k || cur*2 == k) return board[cur] + 1;
 		// 아래는 BFS 부분
		if (board[cur] < board[cur - 1])
		{
			board[cur - 1] = board[cur] + 1;
			q.push(cur - 1);
		}if (board[cur] < board[cur + 1])
		{
			board[cur + 1] = board[cur] + 1;
			q.push(cur + 1);
		}if ((cur * 2 < MAX) && board[cur] < board[cur * 2] )
		{
			board[cur * 2] = board[cur] + 1;
			q.push(cur * 2);
		}
	}
}
int main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	input();
	cout << solve();
}

배열을 미리 INF같은 큰 값으로 초기화해두면 좋다.

BFS같은 경우 처음 방문할 때가 가장 값이 작다는 것이 보장되어 있으므로, 미리 초기화를 해 두고 조건문을 이용하면 visited 배열을 사용한 것과 같은 효과를 낼 수 있다.

예제 입출력 결과