[백준 11729] 하노이 탑 이동 순서

글에 개요

백준 알고리즘 11729번 "하노이 탑 이동 순서" 문제입니다.

재귀함수를 사용하는 대표적인 예로도 사용됩니다!!! 크게 두 가지 제약조건에 대해 고민하고 더 세분화하여 정의하는 부분이 중요합니다.

두 번 세 번 반복하면 분명 도움이 될 것 같아요.

저 또한 알고리즘 테스트에서 최근에 보게 되어 다시 상기하고자 풀어보았습니다.

벌써 2번의 알고리즘 시험에서 보았기 때문에 여러분도 꼭 한 번 풀어보시고, 다른 방법이 없으실지도 고민하시면 좋을 것 같습니다.

[백준 11729] 하노이 탑 이동 순서: https://www.acmicpc.net/problem/11729

참고할 글

1. ..

핵심 내용

1. 제약조건 2가지
1. 원반은 한 번에 하나씩만 옮길 수 있다.
2. 옮기는 과정에서 작은 원반의 위에 큰 원반이 올려져서는 안된다.
2. 아래 그림으로 이해하자!! (총 3가지 STEP이 존재한다.)

   1. 작은 원반 n-1 개를 'A'에서 'B'로 이동

   2. 큰 원반 1 개를 'A'에서 'C'로 이동

  3. 작은 원반 n-1 개를 'B'에서 'C'로 이동

  ▷원반 n개를 이동하는 문제는 원반 n-1개로 이동하는 문제로 세분화되고, 결국 원반 1개를 이동하는 문제로 세분화 된다고 보면 됩니다.

해결 방법

1. 위의 개념을 바탕으로 아래 코드를 보면 쉽게 이해되실 겁니다.

해결한 코드

백준 내용 참고

하노이 탑 이동 순서

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	4113	2130	1610	51.160%

문제

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로  옮기려 한다.

1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.(중간 과정 역시 그래야함)

이 작업을 수행하는데 필요한 이동순서를 출력하는 프로그램을 작성하라

아래 그림은 원판이 5개인 경우의 예시이다.

입력

첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.

 

출력

첫째 줄에 옮긴 횟수 K를 출력한다.

두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.

예제 입력 1 

3

예제 출력 1 

7
1 3
1 2
3 2
1 3
2 1
2 3
1 3