Sign in Subscribe
PS

[PS] BOJ 27440 / 1로 만들기 3

Minjun Kim

• 2 min read
[PS] BOJ 27440 / 1로 만들기 3
문제 링크: https://www.acmicpc.net/problem/27440
Thumbnail: Photo by 青 晨 (Unsplash)

그래프 탐색을 활용해, \(N\)을 1로 만드는 최단 경로를 찾으면 됩니다.

풀이

그래프 탐색

임의의 수 \(X\)에 대해, 수행할 수 있는 연산은 3가지입니다.

  1. \(x\)가 3으로 나누어 떨어지면, 3으로 나눕니다.
  2. \(x\)가 2로 나누어 떨어지면, 2으로 나눕니다.
  3. 1을 뺀다.

이 3가지 연산을 활용해, \(N\)에서 1로 가는 최단 경로를 찾으면 됩니다. 그래프 탐색을 통해 구현할 수 있습니다.

​이번 문제에서는 우선순위 큐 기반의 BFS를 사용했습니다. 해당 수까지 도달하기 위해 시행한 연산의 횟수를 가중치로 사용해 우선순위 큐에 다음 탐색할 수를 추가합니다. 이는 최단 거리가 아닌데 1에 도달하는 경우가 먼저 큐에서 처리되어 정답이 제대로 출력되지 않는 경우를 방지하기 위함입니다.

전체 코드

from heapq import heappush, heappop

input = open(0).readline
N = int(input())

visited = {N: 0}
queue = []
heappush(queue, (0, N))
while queue:
    tries, x = heappop(queue)
    if x == 1:
        print(visited[1])
        break
    # 1. x / 3
    if x % 3 == 0:
        next_x = x // 3
        if not next_x in visited:
            visited[next_x] = tries + 1
            heappush(queue, (visited[next_x], next_x))
    # 2. x / 2
    if x % 2 == 0:
        next_x = x // 2
        if not next_x in visited:
            visited[next_x] = tries + 1
            heappush(queue, (visited[next_x], next_x))
    # 3. x - 1
    next_x = x - 1
    if not next_x in visited:
        visited[next_x] = tries + 1
        heappush(queue, (visited[next_x], next_x))

solution.py