접근법
재귀를 사용하여 코드를 작성하였습니다. start는 출발지, to는 목적지, mid는 거쳐서 가는 중심지 입니다. 원반이 두개일 경우는 1→2, 1→3, 2→3순으로 원반을 옮기고, 세개일 경우에는 1번 기둥에 있는 원반 세개 중 두 개의 원반을 2번 기둥에 옮기고, 가장 큰 원반을 3번 기둥으로 옮깁니다. 두 개의 원반을 옮길 때는 1번 기둥에서 3번기둥을 거쳐 2번 기둥으로 옮기게 됩니다. 마지막으로 2번 기둥에 있는 원반들을 3번 기둥으로 옮겨주면 됩니다.
이를 일반화 시켜 n개의 원반을 옮긴다고 하면, 1번 기둥에 있는 n-1개의 원반을 2번 기둥으로 옮기고, 1번 기둥에 남아 있는 가장 큰 원반을 3번 기둥으로 옮겨줍니다. 또한 2번 기둥에 있는 n-1개의 원반을 3번 기둥으로 옮기면 됩니다.
(1) 원반이 한개일 경우 그냥 3번으로 옮겨주면 됩니다(종료 조건)
(2) 원반이 n개일 경우
① 1번 기둥에 있는 n개의 원반 중 n-1개를 2번 기둥으로 옮깁니다.(3번 기둥을 거쳐감)
② 1번 기둥에 남아 있는 가장 큰 원반을 3번 기둥으로 옮깁니다.
③ 2번 기둥에 있는 n-1개의 원반을 다시 3번 기둥으로 옮깁니다.(1번 기둥을 거쳐감)
위의 경우를 재귀로 푸시면 됩니다!
나의 코드
def hanoi(num, start, to, mid, answer):
#종료조건
if num == 1:
return answer.append([start, to])
#1번 기둥에 있는 n개의 원반 중 n-1개를 2번 기둥으로 옮깁니다.(3번 기둥을 거쳐감)
hanoi(num-1, start, mid, to, answer)
answer.append([start, to])
#2번 기둥에 있는 n-1개의 원반을 다시 3번 기둥으로 옮깁니다.(1번 기둥을 거쳐감)
hanoi(num-1, mid, to, start, answer)
def solution(n):
answer = []
hanoi(n, 1, 3, 2, answer)
return answer
