📄 문제
백준
난이도 : Silver 1
문제 제목 : 1로 만들기 2
✏️ 풀이 1
import sys
from collections import deque
x = int(sys.stdin.readline())
dist = [0] * (x + 1)
pre = [0] * (x + 1)
def bfs(start):
deq = deque([start])
dist[start] = 1
pre[start] = 0
while deq:
c = deq.popleft()
current_cnt = dist[c]
if c == x:
return current_cnt - 1
for nc in (c * 3, c * 2, c + 1):
if nc < 1 or nc > x:
continue
if dist[nc]:
continue
deq.append(nc)
dist[nc] = current_cnt + 1
pre[nc] = c
print(bfs(1))
route = x
while route:
print(route, end=' ')
route = pre[curr]✅ 풀이 한줄 설명:
BFS를 이용하여 1로 가는 최소 연산 횟수를 구한다. 이때, BFS에서 큐에 숫자를 새로 추가할 때 해당 숫자가 어떤 숫자로부터 왔는지를 경로 배열에 기록한다.
✅ 풀이 자세한 설명:
1로 가는 최소 연산 횟수는 BFS를 통해 구할 수 있다. 만약 BFS에 대한 이해가 부족하다면 BFS를 추가적으로 공부해보기를 추천한다. 아래는 기본적인 거리 측정 BFS 문제와 그 풀이를 정리해둔 포스팅이다. 필요에 따라 참고 바란다.
📋 관련 포스팅 : [백준/Python] 2178. 미로 탐색
💫 이 문제와 같이 거쳐온 과정(경로)을 출력하라고 하는 경우, 경로 복원용 테이블 배열을 두는 것을 추천한다.
🍎 1. 기본 BFS 구현하기
우선 1로 가는 최소 연산 횟수를 구하기 위해 1에서부터 n까지 조건에 맞춰 이동시키는 BFS 함수를 구현해보자.
x = int(sys.stdin.readline())
dist = [0] * (x + 1)
def bfs(start):
deq = deque([start])
dist[start] = 1
while deq:
c = deq.popleft()
current_cnt = dist[c]
if c == x:
return current_cnt - 1
for nc in (c * 3, c * 2, c + 1):
if nc < 1 or nc > x:
continue
if dist[nc]:
continue
deq.append(nc)
dist[nc] = current_cnt + 1이 코드를 읽고도 잘 이해가 안된다면 위에 첨부한 미로 탐색 문제 풀이 포스팅을 먼저 공부하는 것을 추천한다.
🍎 2. 경로 복원용 테이블 두기
만약 x = 8이면 경로는 8 -> 2 -> 1 이 될 것이다.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 0 | 1 | 1 | 2 | 4 | 3 | 6 | 4 |
이런 식으로 이번 값이 어디서부터 온 것인지 그 위치를 위와 같은 배열(pre)로 두면 경로 추적이 쉽게 가능하다.
예를 들어 BFS(1)을 실행하면 큐에 3, 2, 1 을 추가하게 되는데, 각 수를 추가할 때 pre[3], pre[2], pre[1] 에 직전 방문한 수인 1을 저장하면 된다.
그러면 pre[i]을 출력했을 때 직전 방문한 수가 어느 곳인지 연쇄적으로 찾을 수 있다.
pre 를 이용하도록 코드를 수정하면 아래와 같다.
x = int(sys.stdin.readline())
dist = [0] * (x + 1)
pre = [0] * (x + 1)
def bfs(start):
deq = deque([start])
dist[start] = 1
pre[start] = 0
while deq:
c = deq.popleft()
current_cnt = dist[c]
if c == x:
return current_cnt - 1
for nc in (c * 3, c * 2, c + 1):
if nc < 1 or nc > x:
continue
if dist[nc]:
continue
deq.append(nc)
dist[nc] = current_cnt + 1
pre[nc] = c📦 GitHub
해당 문제, 풀이에 대한 GitHub Repository 링크는 다음과 같다.
GitHub - 백준(Silver) '12852. 1로 만들기 2'
GitHub - [16강] 시뮬레이션/연습문제 '12852. 1로 만들기 2'
이번 포스팅에서 얻을 수 있었던 풀이 팁은 다음과 같다.
💫 이 문제와 같이 거쳐온 과정(경로)을 출력하라고 하는 경우, 경로 복원용 테이블 배열을 둔다.
