728x90
반응형
재귀가 너무너무 어렵다.
재귀 연습을 위해 기본기에 도움을 준다는 하노이 탑 문제를 풀어보기로 했다.
문제의 이해를 돕기 위해, 예제로 나온 입출력 시, (N==3 일 때)
원판이 어떻게 움직이는 지 영상을 제작했다.
[ 코드 ]
# #17729 하노이 탑 이동 순서
# 0. 입력 값 숫자형으로 변환
# n : 입력받은 숫자
n = int(input())
# rod1, rod2, rod3 : 각 위치에 있는 장대의 번호
def hanoi(n, rod1, rod3, rod2):
## base case
# 원판이 하나일 떄는 그냥 rod1 -> rod3으로 옮기면 끝난다.
if n == 1:
print(rod1, rod3)
## recursion
else:
# 1. 원판 n-1개를 rod1에서 rod2로 옮긴다. (rod3를 보조 기둥으로)
hanoi(n-1, rod1, rod2, rod3)
# 2. n번째 원반 = 제일 밑에 있는 원판을 목적지(rod3)로 이동
print(rod1, rod3)
# 3. rod2(가운데 장대)에 있는 원반 n-1개를 목적지(rod3)로 이동 (rod1를 보조 기둥으로)
hanoi(n-1, rod2, rod3, rod1)
# 테스트
print(n**2 -1)
hanoi(n, 1, 3, 2)[ 해설 ]
음.. 누가 기본이라고 했지?ㅎㅎ
하노이 원탑의 이동 규칙은 아래와 같다.
n개의 원판이 있을 때,
- n-1개의 원판을 1번째 장대에서 2번째 장대로 옮긴다.
(*n-1개의 원판들 : n번 원판(=맨 밑에 있는 원판)을 제외한 나머지 원판들) - n번 원판(=맨 밑에 있는 원판)을 1번째 장대에서 3번째 장대로 옮긴다.
- 나머지 n-1개의 원판들을 다시 2번째 장대에서 3번째 장대로 옮긴다.
이 문제는 원판이 1개일 때, 2개일 때, 3개일 때, .., n개 일 때 점점 n-1일 때의 함수를 재귀로 호출해서,
문제를 해결하는 문제이다.
재귀 문제이기 때문에 base case(재귀가 끝나는 조건) 가 필요하다.
이 문제의 base case는 n이 1일때, 1번째 장대 -> 3번째 장대로 옮기는 값을 출력하며 끝내는 것이다.
n이 그 외의 값일 때는 n==1때까지 계속 n-1로 recursion한다 .
+
이동 횟수는 n²-1번이다.
난 아마.. 이 문제를 이해할 때까지 계속 recursion할꺼같다...
728x90
반응형