[백준] 숨바꼭질 4

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

13913번: 숨바꼭질 4

BFS를 통해 +1, -1, 순간이동(X2)를 통해 도달할 수 있는 모든 경우를 체크해주었습니다. 우선순위 큐를 활용하여 cnt가 낮은 상태가 먼저 나오도록 하여 현재 숫자에 도달할 수 있는 가장 적은 횟수가 visited에 저장되도록 하였습니다. 

 

그 다음으로는 순서를 정하는 방법입니다. K를 시작으로 +1을 통해 도달한 경우, -1을 통해 도달한 경우, 순간이동을 통해 도달한 경우 필요한 횟수와 현재 위치에 필요한 횟수의 차이가 1인 경우에 해당 위치로 이동시키는 방식으로 구현하였습니다.

# 문제링크: https://www.acmicpc.net/problem/13913
import sys, heapq

INT_MAX = sys.maxsize

input = sys.stdin.readline

n, k = tuple(map(int, input().split()))

q = [(0, n)]

visited = [INT_MAX] * 200001


visited[n] = 0
order = []

while q:
    cnt, cur = heapq.heappop(q)

    if cur == k:
        break

    # 1을 빼는 경우
    if cur - 1 >= 0 and visited[cur - 1] > cnt + 1:
        heapq.heappush(q, (cnt + 1, cur - 1))
        visited[cur - 1] = cnt + 1

    # 1을 더하는 경우
    if cur + 1 <= 200000 and visited[cur + 1] > cnt + 1:
        heapq.heappush(q, (cnt + 1, cur + 1))
        visited[cur + 1] = cnt + 1


    # 2배로 곱하는 경우
    if cur * 2 <= 200000 and visited[2 * cur] > cnt + 1:
        heapq.heappush(q, (cnt + 1, 2 * cur))
        visited[2 * cur] = cnt + 1

start = k

for i in range(visited[k]):
    order.append(start)
	
    # +1을 통해 도달한 경우
    if start >= 1 and visited[start - 1] + 1 == visited[start]:
        start = start - 1
        continue
	
    # -1을 통해 도달한 경우
    if start < 200000 and visited[start + 1] + 1 == visited[start]:
        start = start + 1
        continue
	# 순간이동을 통해 도달한 경우
    if start <= 100000 and start % 2 == 0 and visited[start // 2] + 1 == visited[start]:
        start = start // 2

# 시작점을 넣어줌
order.append(n)


print(visited[k])

for i in reversed(order):
    print(i, end=' ')

 

개선된 풀이입니다. 이 문제는 우선순위 큐가 필요하지 않습니다. 이미 방문이 된 숫자들의 경우에는 더 적은 횟수로 방문을 한 경우이기 때문에 단순 큐로도 해결이 가능합니다. 이전과 다른 점은 이전에는 visited에 해당 위치를 방문하기 위해 필요한 이동횟수가 들어있었는데 이번에는 현재 위치에 도달하기 위해 바로 직전에 어떤 위치에 있었는지를 저장하게 됩니다. 만약, 도착점에 도달하게 되면 visited에 저장되어 있는 이전 위치들을 따라가면서 순서들을 찾을 수 있게 되고 순서들의 길이가 필요한 이동 회수가 되게 됩니다. 

 

이전 풀이에서 범위를 200000까지 사용하였는데 그 이유는 K가 100000이라고 가정했을 때 K보다 큰 위치에서 -1이동을 통해 더 적은 횟수로 도달할 수 있는 경우에 대해 생각했기 때문입니다. 하지만 그런 경우는 존재하지 않습니다. 

예를 들어, N < A < B < K이고 B의 2배가 K를 넘고 A의 2배는 넘지 않고 2배를 했을 때 2배를 한 수들로부터 K까지의 거리가 같다고 가정하면 당연히 N에서 A를 만드는 것보다 B를 만드는데 더 많은 횟수가 필요한 것이 자명하기 때문에 제가 생각한 경우는 존재하지 않습니다. 

# 문제링크: https://www.acmicpc.net/problem/13913
import sys
from collections import deque

INT_MAX = sys.maxsize

input = sys.stdin.readline

# 시작점: n, 도착점: k
n, k = tuple(map(int, input().split()))

q = deque([n])

visited = [INT_MAX] * 100001

visited[n] = -1
order = []

while q:
    cur = q.popleft()

    if cur == k:
        while cur != n:
            order.append(cur)
            cur = visited[cur]
        order.append(n)
        break

    # 1을 빼는 경우
    if cur >= 1 and visited[cur - 1] == INT_MAX:
        visited[cur - 1] = cur
        q.append(cur - 1)
    
    # 1을 더하는 경우
    if cur < 100000 and visited[cur + 1] == INT_MAX:
        visited[cur + 1] = cur
        q.append(cur + 1)

    # 순간이동하는 경우
    if cur <= 50000 and visited[2 * cur] == INT_MAX:
        visited[2 * cur] = cur
        q.append(2 * cur)


print(len(order) - 1)
print(*order[::-1])