Sign in Subscribe
PS

[PS] BOJ 13913 / 숨바꼭질 4

Minjun Kim

• 2 min read
[PS] BOJ 13913 / 숨바꼭질 4
문제 링크: https://www.acmicpc.net/problem/13913
Thumbnail: Photo by Dagmar Klauzová (Unsplash)

BFS로 풀 수 있는 숨바꼭질 시리즈입니다. 다만, 이전 숨바꼭질 문제들과는 다르게 "최단 경로" 도 출력해야 합니다.

풀이

BFS

기본적인 풀이는 BFS로 다른 숨바꼭질 문제들과 같습니다. 하지만, 이번 문제는 최단거리로 도달하기 위해 거친 경로를 같이 출력해줘야 합니다.

따라서, 거리 계산은 방문 여부를 기록하는 visited 배열에 방문 여부 대신 해당 위치까지 걸린 시간을 기록하고 (visited[N]이 -1이 아니면 방문한 노드로 판단)

큐에 다음에 방문할 위치를 넣는 대신, [현재까지 방문한 경로 + 다음에 방문할 위치]를 배열의 형태로 큐에 넣었습니다.

예외 처리

굳이 BFS를 하지 않아도 되는 몇 가지 예외가 존재합니다.

  1. \(N = K\)
    이 경우, 수빈이가 동생을 찾는데 걸리는 시간은 0이며, 경로는 \(N\) 하나만 출력하면 됩니다.
  2. \(N > K\)
    이 경우, 현재 위치 \(X\)에서 항상 \(X - 1\)로 이동하는 것이 최선이므로 \(N\)부터 \(K\)까지 1씩 감소시키며 경로를 출력해주면 된다. 걸리는 시간은 \(N - K\)이다.

전체 코드

from collections import deque
input = open(0).readline
N, K = map(int, input().strip().split())
    
if K < N:   # 수빈이가 동생보다 큰 위치에 있다면
    print(N - K)
    print(" ".join(map(str, range(N, K - 1, -1))))
elif K == N:
    print("0")
    print(N)
else:
    queue = deque([[N]])
    visited = [-1 for _ in range(200_002)]
    visited[N] = 0
    while queue:
        current = queue.popleft()
        if current[-1] == K:
            print(visited[current[-1]])
            print(" ".join(map(str, current)))
            break

        for next in (current[-1] * 2, current[-1] - 1, current[-1] + 1):
            if 0 <= next <= 200_000 and visited[next] == -1:
                visited[next] = visited[current[-1]] + 1
                next_path = current.copy()
                next_path.append(next)
                queue.append(next_path)

solution.py