https://school.programmers.co.kr/learn/courses/30/lessons/12946
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
대표적인 재귀문제로 3개의 막대기둥 (A,B,C)가 주어지고 A의 막대기둥에 꽂힌 원판들을 B 막대기둥까지 옮기면 된다.
이때 조건이 주어진다.
- 한번에 하나의 원판만 옮길 수 있다.
- 큰 원판이 작은 원판 위에 있어서는 안 된다.
A기둥에서 B기둥까지 모든 원판을 옮기는 최소 가짓수를 구해보자.
문제 이해
처음에 이 문제를 봤을 때는 재귀의 개념이 쉽게 들어오지 않았다.
원판을 재귀적으로 옮기는건 알겠는데 구체적으로 어떻게 옮기는 거지..?
이걸 어떻게 코드로 구현하는가에서도 막혔다.
n=2 와 n=3일 때를 직접 그려보면 아래와 같다.
여기서 n=2 와 n=3을 비교해 보면 규칙이 나오는 걸 발견할 수 있다.
(1) A에 꽂힌 n-1개의 원판을 B로 전부 옮긴다.
(2) 남은 가장 큰 원판을 A에서 C로 옮긴다.
(3) B에 꽂힌 n-1개의 원판을 전부 C로 옮긴다.
n=2에서 원판을 A에서 C로 옮기는데 3가지 단계를 거친다.
n=3 역시 세가지 과정을 반복하여 원판을 옮긴다.
3단계를 보면 1번규칙이 적용되고, 4단계는 2번 규칙이 적용된다.
이후 다시 5~7단계에서는 3번 규칙에 따라 B에 있던 n-1개의 원판을 C로 옮기는 과정을 반복하게 된다.
이런 방식으로 규칙을 이해하면, n이 몇이든 동일한 구조로 문제를 해결할 수 있다는 걸 알 수 있다.
결국 하노이 탑 문제는 크기가 다른 원판들이 “어떻게 단계적으로 옮겨지는가”를 규칙적으로 나누어 생각하는 게 핵심이다.
풀이 방법
앞서 말했듯이 재귀를 사용하면 된다.
move함수를 따로 만들어 이동 경로를 저장하고, hanoi()함수를 만들어 원판을 옮기는 재귀적인 과정을 구현했다.
hanoi() 함수는 크게 세 단계로 나뉜다:
- Step 1: n-1 개의 원판을 보조 기둥(sub)으로 옮긴다. 이 과정은 hanoi()를 다시 호출해 재귀적으로 수행한다.
- Step 2: 가장 큰 원판( n )을 출발 기둥(start)에서 도착 기둥(end)으로 직접 옮긴다. 이때 move() 함수를 사용해 이동을 기록한다.
- Step 3: 보조 기둥(sub)에 있던 n-1 개의 원판을 다시 도착 기둥(end)으로 옮긴다. 이 과정 역시 hanoi()를 다시 호출해 재귀적으로 수행한다.
풀이 코드
#include <string>
#include <vector>
using namespace std;
vector<vector<int>> moves;
void move(int disk, int start, int end){
moves.push_back({start,end});
}
void hanoi(int n, int start, int end, int sub){
//원판이 한개 뿐이라면 start에서 end로 옮긴다(A->C) 기저사례
if(n==1){
move(1, start, end);
return;
}
//step 1 : n-1개의 원판을 end기둥을 경유하여 start부터 sub까지 옮긴다 (A->B)
hanoi(n-1, start, sub, end);
//step 2 : start위치에서 end위치로 맨 아래 원판을 옮긴다. (A->C)
move(n, start, end);
//step 3 : n-1개의 원판을 sub에서 end까지 start기둥을 경유하여 옮긴다.(B->C)
hanoi(n-1, sub, end, start);
}
vector<vector<int>> solution(int n) {
moves.clear();
hanoi(n,1,3,2);
return moves;
}
내가 도움이 많이 된 블로그도 참조할 테니 보면 좋을 것 같다.
https://shoark7.github.io/programming/algorithm/tower-of-hanoi
'Algorithm > Programmers' 카테고리의 다른 글
[프로그래머스] Lv.0 정수를 나선형으로 배치하기 c++ (0) | 2024.12.30 |
---|---|
[프로그래머스] Lv.3 정수 삼각형 c++ (0) | 2024.12.30 |
[프로그래머스] Lv.2 카펫 c++ (0) | 2024.12.27 |
[프로그래머스] Lv.2 귤 고르기 c++ (0) | 2024.12.27 |
[프로그래머스] Lv.0 배열 회전시키기 c++ (0) | 2023.07.21 |