[백준 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는 정수이다.

출력

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

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

풀이

n에서 k점으로 3가지방법(-1, +1, x2)을통해 최소한의 횟수로 가야한다는것이다.
bfs를 통해 풀수있다.

이때 n과 k사이 관계가 명시되있지않으므로, n이 더클경우를 대비하여 코드를 짜야한다.

방문하는 위치 x마다 큐에넣고, 방문했음을 visited변수로 체크해주면된다. 아주 간단한 bfs코드이다.
이때 visited체크를 큐에 넣기전에 해주어야,
같은값을 여럿 큐에 들어가는 메모리낭비를 방지할수있다.
(=> 큐에서 빼고나서 visited체크를 하면 안된다는 소리)

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>
using std::queue; using std::pair;
int n, k, size;
bool* visited;

int bfs() {
	queue<pair<int, int>> q;
	q.push({ n, 0 });
	visited[n] = true;

	while (!q.empty()) {
		int x = q.front().first;
		int t = q.front().second;
		q.pop();
		if (x == k) return t;

		if (0 <= x - 1 && !visited[x - 1]) {
			visited[x - 1] = true;
			q.push({ x - 1, t + 1 });
		}
		if (x + 1 <= size - 1 && !visited[x + 1]) {
			visited[x + 1] = true;
			q.push({ x + 1,t + 1 });
		}
		if (2 * x <= size - 1 && !visited[2 * x]) {
			visited[2 * x] = true;
			q.push({ 2 * x, t + 1 });
		}
	}

}

int main(void) {
	scanf("%d%d", &n, &k);
	if (n <= k)//2배로 이동할수있으므로 최대크기는 2k + 1
		size = 2 * k + 1;
	else
		size = 2 * n + 1;
	visited = new bool[size]; 
	for (int i = 0; i < size; i++)
		visited[i] = false;

	printf("%d", bfs());

	return 0;
}