BOJ [1697] 숨바꼭질

 

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

 

 

1. 분류

BFS

 

 

 

2. 풀이

 

수빈이의 최소 이동 시간을 계산하는 문제이다.

 

입력으로는 시작점 좌표와 도착점 좌표를 받는다.

 

문제의 조건에서 수빈이는 3가지의 행동을 할 수 있다.

 

1. 현재 있는 위치에서 +1

2. 현재 있는 위치에서 -1

3. 현재 있는 위치의 x2로 순간이동

 

문제에서 주어진 예제는 5, 17이다.

 

5 → 4 → 8 → 16 → 17

5 → 10 → 9 → 18 → 17

 

위의 2가지 방법 정도가 4번만에 도착할 수 있는 최단 거리이다.

 

나올 수 있는 경우의 수들을 그림으로 그려보았다.

 

 

왼쪽 화살표는 -1, 중앙은 +1, 오른쪽은 x2를 한 것이다.

 

그림을 보면 DFS로 풀 수 없는 문제임을 알 수 있다(5 → 4 → 5 → 4 → 5 ...).

 

무한루프가 발생하기 때문이다.

 

그렇다면 BFS로 하되, 속도 향상을 위해선 한 가지의 조건이 더 필요하다.

 

중복된 수를 제거하는 것이다.

 

위의 그림만 보아도 5가 세 개 존재하며 그 아래는 똑같은 가지가 뻗어지기 때문이다.

 

문제에서 0~100,000 사이의 수만 주어지므로 방문을 확인할 배열을 사용하여 해결할 수 있다.

 

 

다음은 답을 도출해내는 시나리오이다.

 

 

먼저 큐에 초기값 5를 넣는다.

 

그 다음 큐의 크기를 구해내고 그 만큼 반복문을 돌린다.

 

반복문 안에서는 q의 최상단 값을 저장한 뒤 pop한다.

 

이 목표값과 일치하는지 검사하고 맞으면 프로그램 종료, 아니면 -1, +1, *2의 순서대로 큐에 삽입한다.

 

반복문이 종료되면 depth를 하나 증가시킨다.

 

지금 큐에는 4, 6, 10이 들어있다.

 

다시 위 과정을 반복해보자.

 

큐의 크기는 현재 3이다.

 

4, 6, 10 순서대로 방문하여 각각 값을 검사하고 -1, +1, *2 순으로 큐에 삽입한다

 

반복문이 종료되면 depth가 증가한다.

 

 

계속 반복시키다 q의 값과 목표지점의 값이 동일한 순간 depth를 정답으로 출력시키면 된다.

 

 

 

 

 

3. 소스코드

#include <cstdio>
#include <queue>

#define MAX 100500
using namespace std;
bool visit[MAX + 1] = { 0 };

int main()
{
	int n, k;

	scanf("%d %d", &n, &k);

	// 예외처리
	if (n == k)
		printf("0\n");

	else
	{
		queue<int> q;
		int depth = 0;

		// 첫 항 삽입
		q.push(n);
		visit[n] = true;

		while (!q.empty())
		{
			int size = q.size();

			for (int i = 0; i < size; i++)
			{
				int v = q.front();
				q.pop();

				// 정답을 찾는 경우 큐를 비우고 프로그램을 종료한다.
				if (v == k)
				{
					printf("%d\n", depth);
					queue<int> empty;
					q = empty;
					break;
				}

				// visit배열을 확인하여 이미 방문한 지점인지 검사. 배열 범위 내의 값만 사용함.
				if (v - 1 >= 0 && !visit[v - 1])
				{
					q.push(v - 1);
					visit[v - 1] = true;
				}
				if (v + 1 <= MAX && !visit[v + 1])
				{
					q.push(v + 1);
					visit[v + 1] = true;
				}
				if (v * 2 <= MAX && !visit[v * 2])
				{
					q.push(v * 2);
					visit[v * 2] = true;
				}
			}

			depth++;
		}
	}

	return 0;
}