[jungol] Beginner_Coder / 재귀 / 1161 / 하노이1 / python

1161 : 하노이1

제한시간5000 ms    메모리제한32 MB    해결횟수718 회    시도횟수1028 회   

문제

하노이의 탑에 대한 전설은 아래와 같다.

고대 인도의 베나레스(현재 베트남의 하노이)​에 있는  한 사원에는 세상의 중심을 나타내는 큰 돔이 있고 

그 안에 세 개의 다이아몬드 기둥이 동판 위에 세워져 있다. 

기둥 가운데 하나에는 신이 64개의 순금 원판을 끼워 놓았다. 

가장 큰 원판이 바닥에 놓여 있고, 나머지 원판들이 점점 작아지며 꼭대기까지 쌓여 있다. 

이것은 신성한 브라흐마의 탑이다. 

브라흐마의 지시에 따라 승려들은 모든 원판을 다른 기둥으로 옮기기 위해 밤낮 없이 차례로 제단에 올라 규칙에 따라 원판을 하나씩 옮긴다. 

이 일이 끝날 때, 탑은 무너지고 세상은 종말을 맞이하게 된다.

 

기둥을 1, 2, 3 번으로 하고, N개의 원판이 작은 것부터 1, 2, 3, 4 … N이라고 할 때, 

아래의 규칙에 따라 모든 원판을 3번 기둥으로 쌓기 위해 이동한다.

1. 한 번에 하나의 원판만 옮길 수 있다.

2. 큰 원판이 작은 원판 위에 있어서는 안 된다.

 

모든 원판이 1번 기둥에 순서대로 쌓여 있을 때, 

최소 횟수로 3번 기둥으로 모두 이동하는 과정을 순서대로 출력하는 프로그램을 작성하시오.

 

 

 

 

입력형식

1번 기둥에 쌓여 있는 원판의 개수 N(1≤N≤15)이 들어온다.

 

출력형식

한 줄에 한 개의 원판을 이동하는 과정을 “원판번호 : 이동전 기둥번호 -> 이동후 기둥번호” 형식으로 모두 출력한다.

 

입력

3

출력

1 : 1 -> 3
2 : 1 -> 2
1 : 3 -> 2
3 : 1 -> 3
1 : 2 -> 1
2 : 2 -> 3
1 : 1 -> 3

 

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=441&sca=2080 

JUNGOL

 

💥접근방법

하노이의 탑을 진행하는 논리는 위와 같다. 이 부분은 그림을 봐도 이해되고 조금만 구글링하면 나오니 패스! 이 부분보다 이 하노이의 탑 과정을 재귀함수로 구현하는 부분이 정말 이해가 안갔었다. 그래서 재귀함수로 하노이의 탑 도출 과정을 정리해보았다.

 

🔥가장 중요한 point

함수호출은 return해서 나갈 구멍이 없으면 stack에 쌓이고 다시 돌아왔을때 자기가 호출됐었던 위치 바로 아래코드부터 실행한다.

 

빨간색 숫자 : 함수 호출 순서

초록색 숫자 : 과정 print 순서

 

👀 코드구현