티스토리 뷰
🔷 백준 1로 만들기 2 12852 Python
✅ 문제 설명
문제
정수 N이 주어집니다. 다음 연산을 사용하여 N을 1로 만들려고 합니다.
- N이 3으로 나누어 떨어지면, N을 3으로 나누기
- N이 2로 나누어 떨어지면, N을 2로 나누기
- N에서 1 빼기
연산은 여러 번 사용할 수 있고, 같은 연산을 반복해도 됩니다. 목표는 연산을 사용하는 횟수를 최소로 하여 N을 1로 만드는 것입니다. 또한, 최소 횟수를 달성하는 과정에서 거치는 수들을 순서대로 출력해야 합니다.
테스트케이스
입력 1
2출력 1
1
2 1입력 2
10출력 2
3
10 9 3 1문제 설명
예를 들어 N이 2라면, 2를 2로 나누어 1로 만들 수 있습니다. 이 경우 연산 횟수는 1번이며, 경로는 2 → 1입니다. N이 10이라면, 여러 경로가 가능합니다.
- 10 → 5 → 4 → 3 → 2 → 1 (연산 5번)
- 10 → 8 → 4 → 2 → 1 (연산 4번)
- 10 → 9 → 3 → 1 (연산 3번, 최소)
이 비교를 통해 단순히 나누기나 빼기를 반복하는 것이 아니라, 전체 경로 중 최소 횟수를 주는 방법을 선택해야 한다는 점이 드러납니다. 10의 경우, 가장 적은 연산 횟수는 3이며, 과정은 다음과 같습니다.
- 1단계: 10에서 1을 빼서 9로 만든다.
- 2단계: 9를 3으로 나누어 3을 만든다.
- 3단계: 3을 3으로 나누어 1을 만든다.
✅ 아이디어
BFS는 최단, 최소거리에 사용될 수 있습니다.
BFS(Breadth-First Search, 너비 우선 탐색)는 그래프나 트리에서 최소 거리, 최소 단계, 최단 경로를 구할 때 매우 유용한 방법입니다. 그 핵심 이유는 BFS가 탐색할 때 한 단계(레벨)에 속하는 모든 노드를 완전히 처리한 다음에야 다음 단계로 이동하기 때문입니다. 이 특성 때문에, 어떤 노드를 처음 방문하는 순간 그 거리가 바로 최단 거리가 됩니다.
일상적으로 비유하자면, 사람이 건물의 층을 탐색할 때 엘리베이터를 타지 않고 한 층 전체를 다 둘러본 뒤 다음 층으로 올라가는 것과 같습니다. 이 경우, 처음 발견한 사무실이 그 층에서 가장 가까운 위치인 것처럼, BFS도 가장 가까운 경로를 먼저 찾아냅니다.
기본 구조 설정
예시로 사용할 트리는 다음과 같습니다.
1 level 1
/ \
2 3 level 2
/ \ \
4 5 6 level 3
|
7 level 4
여기서
- 노드(Node): 각 숫자를 의미합니다.
- 레벨(Level): 시작점(여기서는 1번)으로부터의 단계 수를 의미합니다.
정리하면,
- Level 1: 시작점 1
- Level 2: 1에서 직접 연결된 2, 3
- Level 3: 2에서 연결된 4, 5, 그리고 3에서 연결된 6
- Level 4: 5에서 연결된 7
BFS 진행 원리
1단계 – 시작점 방문
처음에는 시작점만 존재합니다. BFS는 항상 시작점에서 출발합니다.
[1] level 1
/ \
2 3 level 2
/ \ \
4 5 6 level 3
|
7 level 4
이 시점에서 아직 다른 노드를 방문하지 않았습니다. 1번 노드와의 거리는 0이므로, 1은 시작점이자 가장 가까운 노드입니다.
2단계 – Level 2 방문
시작점 1과 연결된 모든 노드(2, 3)를 다음 방문 대상으로 둡니다. BFS는 “왼쪽부터 오른쪽”이라는 고정 순서가 아니라, 발견한 순서대로 처리하지만, 핵심은 한 레벨 전체를 처리하고 나서만 다음 레벨로 넘어간다는 점입니다.
1 level 1
/ \
[2] [3] level 2
/ \ \
4 5 6 level 3
|
7 level 4
여기서 중요한 점은, 이 순간에 2와 3까지의 거리는 정확히 1이라는 사실입니다. 만약 더 짧은 경로가 있었다면, BFS의 구조상 반드시 이 전에 방문했을 것입니다.
3단계 – Level 2 처리 순서
먼저 2를 처리합니다. 2와 연결된 4, 5를 다음 대상에 추가합니다.
1 level 1
/ \
[2] 3 level 2
/ \ \
[4] [5] 6 level 3
|
7 level 4
그 다음 3을 처리하고, 3과 연결된 6을 다음 대상에 추가합니다.
1 level 1
/ \
2 [3] level 2
/ \ \
4 5 [6] level 3
|
7 level 4
여기서도, 4, 5, 6이 모두 거리 2인 이유는 BFS가 한 단계씩 확장하며 방문하기 때문입니다.
4단계 – Level 3 방문 시작
이제 레벨 3의 모든 노드를 차례대로 처리합니다. 4부터 처리합니다. 4는 자식 노드가 없으므로 새로운 방문 대상이 없습니다.
1 level 1
/ \
2 3 level 2
/ \ \
[4] 5 6 level 3
|
7 level 4
이것이 BFS가 불필요하게 더 먼 노드를 먼저 방문하지 않는 원리입니다.
5단계 – Level 3 계속
다음으로 5를 처리합니다. 5는 자식 노드 7을 갖고 있으므로, 7을 다음 방문 대상으로 둡니다.
1 level 1
/ \
2 3 level 2
/ \ \
4 [5] 6 level 3
|
[7] level 4
여기서 7은 처음 발견된 시점에서 거리 3이라는 것이 확정됩니다. 왜냐하면 BFS의 특성상, 그보다 가까운 경로가 있다면 이미 이전 단계에서 발견됐을 것이기 때문입니다.
6단계 – Level 3 마지막
6을 처리합니다. 6은 자식이 없으므로 새로운 방문 대상이 없습니다.
1 level 1
/ \
2 3 level 2
/ \ \
4 5 [6] level 3
|
7 level 4
7단계 – Level 4 방문
마지막으로 7을 처리하면 탐색이 끝납니다.
1 level 1
/ \
2 3 level 2
/ \ \
4 5 6 level 3
|
[7] level 4
BFS가 최단 경로를 보장하는 이유
BFS는 가까운 거리의 노드를 먼저 전부 방문한 후, 더 먼 거리에 있는 노드로 이동합니다. 따라서 어떤 노드를 처음 발견했을 때의 거리가 바로 그 노드까지의 최단 거리입니다. 예를 들어, 5에 도달하는 경우를 보면, 1 → 2 → 5가 가장 짧은 경로인데, BFS는 1 방문 → 2 방문 → (다음 단계에서) 5 방문 이 순서를 반드시 지키므로 더 짧은 경로를 놓칠 수 없습니다.
문제를 BFS로 표현하기
처음에 주어진 예시 입력인 N = 10을 이용해서 BFS의 원리를 자세히 알아보겠습니다. 각각의 숫자를 그래프의 노드로 생각하고, 가능한 세 가지 연산을 간선으로 연결합니다. 처음 노드 10에서 출발할 때 가능한 연산은 다음과 같습니다.
- 10이 3으로 나누어 떨어지지 않으므로 3으로 나누기 불가능
- 10이 2로 나누어 떨어지므로, 2로 나눈 숫자
5로 이동 가능 - 숫자 1을 빼서,
9로 이동 가능
[10] level 1
/ \
5 9 level 2
✅ BFS는 항상 현재 노드(숫자)에서 가능한 모든 다음 노드를 찾은 후, 다음 레벨(Level)로 이동합니다. 이렇게 레벨을 하나씩 내려가면서 탐색하기 때문에, 최초로 발견되는 노드가 항상 최단 거리임이 보장됩니다. 여기서 나타난 노드 5와 9는 10에서 한 번의 연산만으로 도달 가능한 노드들입니다. 따라서, 5와 9로 가는 더 빠른 경로는 존재하지 않습니다.
이제 다음 단계로 넘어갑니다. 두 번째 레벨(Level 2)에서 나온 노드들(5, 9)을 각각 하나씩 확인합니다. 먼저 노드 5에서 가능한 연산을 확인하면,
- 5는 3으로 나누어지지 않습니다.
- 5는 2로도 나누어지지 않습니다.
- 1을 빼는 연산만 가능해서, 숫자
4로 이동합니다.
다음으로 노드 9에서 가능한 연산을 확인하면,
- 9는 3으로 나누어져서 숫자
3으로 이동합니다. - 9는 2로 나누어지지 않으므로, 2로 나누기는 불가능합니다.
- 1을 빼는 것이 가능하므로 숫자
8로 이동합니다.
[10] level 1
/ \
5 9 level 2
/ / \
4 3 8 level 3
✅ 이 레벨 3에서 등장한 숫자들(4, 3, 8)은 최초 숫자 10에서 정확히 두 번의 연산만으로 도달할 수 있는 숫자입니다. 즉, 연산을 두 번 이하로 사용해 이 숫자들에 도착하는 더 짧은 경로는 존재하지 않습니다.
다음 레벨(Level 3)의 숫자들(4, 3, 8)을 각각 하나씩 확인합니다.
- 먼저 노드 4에서 가능한 연산을 보면,
- 4는 3으로 나누어지지 않으므로 3으로 나누기 불가능.
- 4는 2로 나누어져서 숫자
2로 이동 가능. - 1을 빼서 숫자
3으로 이동 가능한데, 이때 숫자 3은 이미 앞에서 방문했으므로 다시 가지 않습니다. (중복 방문 X) - 다음 노드 3에서 가능한 연산을 보면,
- 3은 3으로 나누어져서 숫자
1로 이동 가능합니다. ✅여기서 목적지인 숫자 1이 최초로 발견됩니다. - 3은 2로 나누어지지 않으므로 불가능.
- 1을 빼서 숫자
2로도 이동 가능하지만, 이미 방문했으므로 건너뜀 (X). - 마지막 노드 8에서 가능한 연산을 보면,
- 8은 3으로 나누어지지 않습니다.
- 8은 2로 나누어져서 숫자
4로 이동 가능한데, 4는 이미 앞에서 방문했으므로 중복 방문하지 않습니다 (X). - 1을 빼서 숫자
7로 이동 가능합니다.
[10] level 1
/ \
5 9 level 2
/ / \
4 3 8 level 3
/ / \
2 1 7 level 4
여기서 노드 1이 최초로 발견됐습니다. 이 시점에서 숫자 1까지 가는 최소 횟수가 결정됩니다. ✅ 여기서 발견된 숫자 1이 최소 횟수로 도착한 숫자라는 것이 BFS의 핵심 특성입니다. 왜냐하면, 이전 레벨(Level 1~3)을 모두 탐색했지만 숫자 1을 발견하지 못했고, 이번 레벨(Level 4)에서 처음 숫자 1이 발견됐기 때문입니다. 이것보다 더 짧은 경로가 존재한다면, 반드시 이전 레벨에서 발견됐을 것입니다. 그러므로 최단 경로는 10 → 9 → 3 → 1 이고, 최소 연산 횟수는 3회입니다.
✅ 지금까지의 탐색 과정을 다시 한 번 강조해서 요약하면 다음과 같습니다.
✅ 역추적을 통한 최종 경로 찾기 방법
마지막으로, BFS 탐색을 할 때는 어떤 숫자에서 현재 숫자로 이동했는지를 함께 기록하면, 최종 답까지의 경로를 쉽게 구할 수 있습니다. 위 경우에서 보면,
- 숫자 1은 숫자 3에서 왔고,
- 숫자 3은 숫자 9에서 왔고,
- 숫자 9는 숫자 10에서 왔습니다.
이렇게 목적지인 숫자 1에서 출발하여 위쪽으로 부모 노드를 따라 올라가면 최종 경로가 역순으로 나옵니다. ✅ 즉, 1 → 3 → 9 → 10의 순서로 역추적되며, 이 경로를 뒤집으면 10 → 9 → 3 → 1 로 원하는 정답 경로를 얻을 수 있습니다.
✅ 전체 코드
import queue
N=int(input())
parent=[0 for _ in range(N+1)]
check=[0 for _ in range(N+1)]
q=queue.Queue()
st=[]
q.put(N)
check[N]=1
parent[N]=-1
while not q.empty():
k=q.get()
if k==1:
print(check[k]-1)
st.append(k)
j=k
while j!=-1:
j=parent[j]
st.append(j)
else:
if k%3==0 and check[k//3]==0:
q.put(k//3)
check[k//3]=1+check[k]
parent[k//3]=k
if k%2==0 and check[k//2]==0:
q.put(k // 2)
check[k // 2] = 1+check[k]
parent[k // 2] = k
if check[k-1]==0:
q.put(k-1)
check[k-1]=1+check[k]
parent[k-1]=k
st.pop()
for i in range(len(st)):
print(st.pop(),end=' ')
✅ 개별 코드 설명
수형도의 확장 설명
1. q에 값을 집어넣었다는 것은 그 계층을 방문하겠다는 의미입니다.
q=queue.Queue()
q.put(10)
check[10] = 0
parent[10] = -1
이 코드를 입력하면 다음과 같은 수형도가 형성됩니다.
[10] level 1
2. while문으로 이제 모든 곳을 돌아야 합니다. 종료조건은 큐가 빌 때, 즉 모든 노드를 다 돌았을 때입니다.
while not q.empty():
k=q.get()
지금 이제 10을 확인합니다. 10에 이어진 경우는 다음 세 가지가 있습니다.
- 3으로 나누어지는 경우
- 2로 나누어지는 경우
- -1을 빼는 경우
10은 3으로 나누어지지 않으므로 두 가지 갈래가 생깁니다.
[10] level 1
/ \
5 9 level 2
이때 우리는 나중에 10→5 혹은 10→9로 경로를 출력하기 위해, 그리고 중복 방문을 방지하기 위해 check 배열과 parent 배열을 같이 업데이트합니다.
if k%3==0 and check[k//3]==0:
q.put(k//3)
check[k//3]=1+check[k]
parent[k//3]=k
if k%2==0 and check[k//2]==0:
q.put(k // 2)
check[k // 2] = 1+check[k]
parent[k // 2] = k
if check[k-1]==0:
q.put(k-1)
check[k-1]=1+check[k]
parent[k-1]=k
q = [5, 9]
check[5] = 1, parent[5] = 10
check[9] = 1, parent[9] = 10
3. 이제 반복문을 한 번 더 돕니다. 이번에는 q의 맨 앞에 있는 5를 꺼냅니다. 5에서 가능한 경우는 다음과 같습니다.
- 3으로 나누어지는 경우 → 불가능
- 2로 나누어지는 경우 → 불가능
- -1을 빼는 경우 → 4
따라서 4를 새로 큐에 넣습니다.
[10] level 1
/ \
5 9 level 2
/
4 level 3
q = [9, 4]
check[4] = 2, parent[4] = 5
4. 다음으로 q에서 9를 꺼냅니다. 9에서 가능한 경우는 다음과 같습니다.
- 3으로 나누어지는 경우 → 3
- 2로 나누어지는 경우 → 불가능
- -1을 빼는 경우 → 8
따라서 3과 8을 큐에 넣습니다.
[10] level 1
/ \
5 9 level 2
/ / \
4 3 8 level 3
q = [4, 3, 8]
check[3] = 2, parent[3] = 9
check[8] = 2, parent[8] = 9
5. 다음으로 q에서 4를 꺼냅니다. 4에서 가능한 경우는 다음과 같습니다.
- 3으로 나누어지는 경우 → 불가능
- 2로 나누어지는 경우 → 2
- -1을 빼는 경우 → 3 (이미 방문했으므로 건너뜀)
따라서 2만 큐에 넣습니다.
[10] level 1
/ \
5 9 level 2
/ / \
4 3 8 level 3
/
2 level 4
q = [3, 8, 2]
check[2] = 3, parent[2] = 4
6. 다음으로 q에서 3을 꺼냅니다. 3에서 가능한 경우는 다음과 같습니다.
- 3으로 나누어지는 경우 → 1 (목표 도달)
- 2로 나누어지는 경우 → 불가능
- -1을 빼는 경우 → 2 (이미 방문했으므로 건너뜀)
1을 큐에 넣고 종료할 수 있습니다.
[10] level 1
/ \
5 9 level 2
/ / \
4 3 8 level 3
/ /
2 1 level 4
check[1] = 3, parent[1] = 3
이제 parent 배열을 이용하면 1에서 거꾸로 올라가 경로를 복원할 수 있습니다.
1 → 3 → 9 → 10
즉, 최소 연산 경로는 10 → 9 → 3 → 1입니다.
parent 배열을 이용한 역추적 코드 설명
1. 처음 시작점 N=10을 큐에 넣습니다.
q=queue.Queue()
q.put(10)
parent[10] = -1 # 시작점이므로 부모 없음
check[10] = 1 # 방문 체크
이 시점의 수형도는
[10] level 1
아직 자식 노드가 없습니다.parent[10] = -1 : 10은 시작점이므로 부모가 없습니다.
2. 큐에서 10을 꺼내고, 10에서 가능한 연산을 적용합니다.
- 3으로 나누기 → 불가능 (나누어떨어지지 않음)
- 2로 나누기 → 5 생성
- -1 → 9 생성
[10] level 1
/ \
5 9 level 2
parent[5] = 10 : 5의 부모는 10입니다.parent[9] = 10 : 9의 부모는 10입니다.
이때 check[5]와 check[9]도 각각 1로 설정되어, 다시 방문하지 않도록 합니다.
3. 큐 상태는 이제 다음과 같습니다.
q = [5, 9]
5와 9가 다음에 탐색될 노드입니다.
4. 큐에서 5를 꺼내고, 가능한 연산을 적용합니다.
- 3으로 나누기 → 불가능
- 2로 나누기 → 불가능
- -1 → 4 생성
[10] level 1
/ \
5 9 level 2
/
4 level 3
parent[4] = 5 : 4의 부모는 5입니다.check[4]도 업데이트되어 다시 방문하지 않도록 합니다.
5. 큐 상태는 이제 다음과 같습니다.
q = [9, 4]
6. 큐에서 9를 꺼내고, 가능한 연산을 적용합니다.
- 3으로 나누기 → 3 생성
- 2로 나누기 → 불가능
- -1 → 8 생성
[10] level 1
/ \
5 9 level 2
/ / \
4 3 8 level 3
parent[3] = 9 : 3의 부모는 9입니다.parent[8] = 9 : 8의 부모는 9입니다.
이 역시 처음 방문하는 노드이므로 parent가 정확하게 저장됩니다.
7. 큐 상태는 다음과 같습니다.
q = [4, 3, 8]
8. 큐에서 4를 꺼내고, 가능한 연산을 적용합니다.
- 3으로 나누기 → 불가능
- 2로 나누기 → 2 생성
- -1 → 3 생성 (하지만 이미 방문했으므로 무시)
[10] level 1
/ \
5 9 level 2
/ / \
4 3 8 level 3
/
2 level 4
parent[2] = 4 : 2의 부모는 4입니다.
9. 큐 상태는 다음과 같습니다.
q = [3, 8, 2]
10. 큐에서 3을 꺼내고, 가능한 연산을 적용합니다.
- 3으로 나누기 → 1 생성
- 2로 나누기 → 불가능
- -1 → 2 생성 (이미 방문했으므로 무시)
[10] level 1
/ \
5 9 level 2
/ / \
4 3 8 level 3
/ /
2 1 level 4
parent[1] = 3 : 1의 부모는 3입니다.
11. 여기서 1을 발견했으므로 BFS 탐색이 종료됩니다. 1이 생성된 순간, 다음과 같이 parent 배열이 완성됩니다.
parent[1] = 3 → 1의 부모는 3입니다.parent[3] = 9 → 3의 부모는 9입니다.parent[9] = 10 → 9의 부모는 10입니다.parent[10] = -1 → 10은 시작점입니다.
이렇게 1에서 시작하여 parent 값을 따라가면 최단 경로를 거꾸로 얻을 수 있습니다.
역추적 예시 (1에서 시작)
현재 노드 = 1 → parent[1] = 3
현재 노드 = 3 → parent[3] = 9
현재 노드 = 9 → parent[9] = 10
현재 노드 = 10 → parent[10] = -1 (시작점 도착)
역추적 결과 (거꾸로 저장된 값)
1 → 3 → 9 → 10
이를 뒤집으면 실제 경로가 나옵니다.
10 → 9 → 3 → 1
✅ 결론
- BFS를 사용하면 큐(
q)에 값이 들어가는 순간, 해당 노드의 부모(parent)를 함께 기록하기 때문에 역추적이 가능합니다. parent배열은 “현재 노드가 어떤 노드에서 왔는지”를 저장하는 역할을 하며, 이는 중복 방문을 막는check배열과 함께 사용됩니다.- 목표값(여기서는 1)이 큐에 들어오면,
parent값을 거슬러 올라가면 시작점에서 목표값까지의 최단 경로를 얻을 수 있습니다. - 역추적 시 경로가 거꾸로 나오므로, 이를 뒤집으면 실제 최소 연산 경로를 출력할 수 있습니다.
'백준 스터디' 카테고리의 다른 글
| 백준 10799번 쇠막대기 Python (0) | 2025.08.02 |
|---|---|
| 백준 10799번 쇠막대기 문제 풀이 (0) | 2025.08.02 |
| 백준 12852번 1로 만들기 2 C++ (0) | 2025.08.01 |
| 백준 1759번 – 암호 만들기 (Python) (3) | 2025.07.31 |
| 백준 1759번 암호 만들기 C++ (2) | 2025.07.31 |
- Total
- Today
- Yesterday
- C++
- 백준
- 프로그래밍
- 동적 계획법
- 문자열처리
- c언어
- 코딩 테스트
- DP
- 그래프 탐색
- 그리디알고리즘
- 동적계획법
- 브루트포스
- 알고리즘기초
- 코딩테스트
- 상속
- HTML
- 객체지향
- 알고리즘
- python 알고리즘
- 문제 풀이
- 파이썬
- 프로그래머스
- 알고리즘문제풀이
- 코딩
- dfs
- Python
- 알고리즘 문제풀이
- 문제풀이
- 그리디
- 파이썬코딩
| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 1 | ||||||
| 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| 16 | 17 | 18 | 19 | 20 | 21 | 22 |
| 23 | 24 | 25 | 26 | 27 | 28 | 29 |
| 30 |