12851: 숨바꼭질 2

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

12851번: 숨바꼭질 2

설명

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

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

핵심 아이디어

• 두 개의 위가 주어졌을 때, 한 위치에서 다른 위치로 이동하는 가장 빠른 시간과 방법을 구하는 문제이므로 BFS 탐색 알고리즘을 떠올리면 좋다. 
• x-1, x+1, x*2 를 고려해서 범위 내에 있고, 방문하지 않았거나 방문 했더라도 이전 지점에서 재방문 할 수 있을 경우의 조건을 넣어야 한다. 
• 그리고 K값이 되면, 방문 거리와 방문 횟수를 저장해 주었다. 그리고 연산이 처음부터 돌아가야 하므로 continue를 넣어 주었다. (continue를 넣지 않으면 중간 테스트케이스에서 틀려버린다.)

코드 구현

Python

import sys
input = sys.stdin.readline
from collections import deque

start, k = map(int, input().split())
distance = [0] * 100001 # 최대 0부터 100000지점까지 걸리는 횟수 기록
#bfs 탐색 알고리즘
q = deque()
q.append(start) # 수빈이가 있는 시작 위치

min_distance = 0 # 최적 시간
cnt = 0 # 최적의 경로의 수

while q:
	x = q.popleft()
	# 도작 지점이라면 탐색 종료
	if x == k: # 방문 시간과 방문 횟수 저장
		min_distance = distance[x]
		cnt += 1
		continue # 다른 최단 방법을 찾기 위해 연산을 처음부터 하기 위함
	for next in (x+1, x-1, x*2):
		# 주어진 범위를 벗어나지 않고, 방문하지 않았거나 다음 지점 의 최단 거리가
		# 이전 지점 + 1 이라면 즉, 동일한 최단 거리 기록을 갖는 곳
		# 중요한 점은 동일한 탐색 횟수를 가진 곳도 재탐색 해야한다.
		# 이를 통해 이미 탐색 했던 곳도 포함해서 다양한 최단 경로 탐색 가능
		if (0<= next <= 100000) and (distance[next] == 0 or
		distance[next] == distance[x] + 1):
			distance[next] = distance[x] + 1 # 방문하고 횟수 1 늘림
			q.append(next)
print(min_distance)
print(cnt)

C++

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;

int start, k;
vector<int> distance; // 최대 0부터 100000까지의 횟수 기록


int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> start >> k;
	// distance 초기화
	vector<int> distance(100001, 0);

	// 큐 구현을 위해 deque 사용
	queue<int> q;
	q.push(start); // 수빈이가 있는 시작 위치

	int min_distance = 0; // 최적 시간
	int cnt = 0; // 최적의 경로의 수

	while (!q.empty()) {
		int x = q.front();
		q.pop();

		// 도착 지점이라면
		if (x == k) {
			min_distance = distance[x]; // 첫 도착 시간 기록
			cnt++; // 같은 최단 거리일 경우 카운트 증가
			continue;
		}

		for (int next : {x + 1, x - 1, x * 2}) {
			// 주어진 범위를 벗어나지 않고, 방문하지 않았거나 
			// 다음 지점의 최단 거리가 이전 지점 + 1 이라면
			if (0 <= next && next <= 100000 &&
				(distance[next] == 0 || distance[next] == distance[x] + 1)) {
				distance[next] = distance[x] + 1; // 방문 하고 횟수 1 늘림
				q.push(next);
			}
		}
	}
	cout << min_distance << "\n";
	cout << cnt << "\n";

	return 0;
}

여기서 중요한 점은 '동일한 탐색 횟수를 가진 곳'도 탐색한다는 것이다. 즉 이미 탐색 했던 곳도 포함해서 다양한 최단 경로를 탐색할 수 있다. 그렇지 않으면, 앞선 최단 경로가 지나간 경로는 사용할 수 없으므로 모든 경우의 수를 구할 수 없다.