JUST WRITE IT. HomeArchivesTagsCategories
백준 11729번 하노이 탑 이동 순서
|AlgorithmBOJ|

#11729. 하노이 탑 이동 순서

Problem

  • N개의 원판
  • 첫 번째 장대 → 세 번째 장대
  • 한 번에 한 개의 원판만 다른 탑으로 이동 가능
  • 원판 위 < 원판 아래
  • 원판 이동 순서 최소화

Solution

굳이 이를 최소화시키는 방법을 생각하기보다 컴퓨터가 알아서 최소의 방법을 계산하도록 하자. → 하노이 탑도 알고리즘이 존재

  • 먼저 하나의 원판만 있을 때를 생각해보자

보조 기둥 필요없이 바로 목표 기둥으로 이동하면 된다.

1
2
3
4
5
6
7
// recursive frame
void move(원반 개수, 시작, 보조, 목표) { }

if(원반의 개수 == 1) {
	시작->목표
	return;
}

원반의 개수가 1보다 클때는 어떻게 해야 할까?

가장 큰 원반을 제외한 모든 원반이 보조 기둥에 있어야 한다. → 이게 포인트


1
2
// 맨 아래에 있는 원반을 제외한 모든 원반을 보조 기둥으로 옮긴다.
move(원반개수-1, 시작, 목표, 보조); // 시작 -> 보조

그러면 가장 큰 원반은 이 부분이 적용된다.
1
2
3
4
if(원반의 개수 == 1) {
	시작->목표
	return;
}

가장 큰 원반이 목표 기둥으로 이동하였고, 이제 이 원반은 없는 것으로 보아도 무방하다. 나머지 원반들이 모든 기둥을 이동할 수 있기 때문이다.

그러면 이제 다시 n-1개의 원반을 가지고 위와 같은 작업을 진행한다.
이때는 원래 보조 기둥을 시작 기둥으로, 시작 기둥을 보조 기둥으로 생각해야 한다.


1
move(원반개수-1, 보조, 시작, 목표);

Recursive frame의 내용을 완성해보자.
1
2
3
4
5
6
7
8
9
void move(int count, int start, int temp, int goal) {
	if(count == 1) {
        // start -> goal
        return;
    }
    move(count-1, start, goal, temp); // start->temp
    // start -> goal
    move(count-1, temp, start, goal); // temp->goal
}

주석으로 되어 있는 부분은 실질적으로 어떤 기둥에서 어떤 기둥으로 원반이 움직였는지를 나타내는 부분이다.

좀 더 깊은 이해를 위해 원반의 개수가 3개일 때 재귀함수 호출 순서를 작성하였다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
move(3, 1, 2, 3)
	move(2, 1, 3, 2) // 1, 2번 원반이 2번 기둥으로 가는 과정
		move(1, 1, 2, 3) 
			1에서 3으로 이동 (1번 원반)
			1에서 2로 이동 (2번 원반)
		move(1, 3, 1, 2)
			3에서 2로 이동(1번 원반)
	1에서 3으로 이동(3번 원반)
	move(2, 2, 1, 3) // 1, 2번 원반이 3번 기둥으로 가는 과정
		move(1, 2, 3, 1)
			2에서 1로 이동(1번 원반)
			2에서 3으로 이동(2번 원반)
		move(1, 1, 2, 3)
			1에서 3으로 이동 (1번 원반)

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <vector>
using namespace std;
vector<pair<int, int>> answer;
void move(int count, int start, int temp, int goal) {
	if(count == 1) {
        answer.push_back(make_pair(start, goal));
        return;
    }
    move(count-1, start, goal, temp); // start->temp
    answer.push_back(make_pair(start, goal));
    move(count-1, temp, start, goal); // temp->goal
}

int main() {
   int n;
   cin >> n;
   move(n, 1, 2, 3);
   cout << answer.size() << "\n";
   for(auto v : answer) {
       cout << v.first << " " << v.second << "\n";
   }
   return 0;
}

이동 횟수부터 출력해야 하므로, pair를 만들어 vector에 넣어주었다.

Algorithm