문제 분석
문제
하노이탑 문제이다. 하노이탑은 총 3개의 장대가 있으면 처음 상태의 탑을 다른 장대로 모두 완전히 옮기는 것을 의미한다. 순서는 큰 원판부터 작은 원판 순으로 배치해야 한다.
입력과 출력
입력은 단순하다. 하노이탑에 넣을 원판의 개수만 받는다.
출력은 먼저 총 이동 횟수를 보여준다. 그리고 그 다음 줄부터 이동 경로를 출력한다. 이동경로는 시작점과 도착지만 표시한다. 즉 탑에서 제일 위에 있는 원판만 꺼낸다고 가정하고 원판 번호는 출력하지 않은 채 이동경로만 표시한다.
예제
예제는 다음과 같다.
3개의 원판이 주어진다고 하면
- 1번 원판이 1번 장대에서 3번 장대로 이동한다.
- 2번 원판이 1번 장대에서 2번 장대로 이동한다.
- 1번 원판이 3번 장대에서 2번 장대로 이동한다.
- 3번 원판이 1번 장대에서 3번 장대로 이동한다.
- 1번 원판이 2번 장대에서 1번 장대로 이동한다.
- 2번 원판이 2번 장대에서 3번 장대로 이동한다.
- 1번 원판이 1번 장대에서 3번 장대로 이동한다.
이 과정을 통해 진행되는데 입력과 출력에서 설명한 것 처럼 글자가 강조된 부분만 출력한다고 생각하면 된다.
코드분석
하노이 재귀함수 생성
def hanoi(n, start, end, sub):
global cnt
if n==1:
move(1,start, end)
return
else:
hanoi(n-1, start, sub, end)
move(n, start, end)
hanoi(n-1, sub, end, start)일단 hanoi(n-1, start, sub,end)를 이용해 2번으로 모두 보낸다. start는 고정되어 있고 sub, end를 번갈아 가면서 이동하게 되는 것이다. 그리고 나서 다시 sub인 2번에서 3번으로 옮기게 된다. 이 과정에서 옮기는 기둥들을 설명하기 위해 move라는 함수를 이용해서 보이는 것이다. n=1이라면 1번으로 끝나기에 이는 분리해서 if문으로 빼준다.
처음 hanoi를 이용해 2번 원판으로 이동하고 난 뒤에 상태를 모두 move로 학 나서 다시 3번 장대로 이동하기 위해 hanoi를 이용해 최종적으로 3번원판으로 이동한다.
이동 상태 함수 생성
def move(n,start, end):
global cnt
result.append([start, end])
cnt+=1그리고 하노이 함수에서 보게 되면 move라는 호출이 나오게 된다. 이 함수는 이동 상태를 나타내기 위해 생성하였다. start와 end를 최종 결과를 출력하기 위한 리스트인 result에 추가한다. 그리고 전역 변수를 이용해 몇번 이동하는지 카운트를 해준다.
함수 외 부분
hanoi(n,1, 3, 2)
print(cnt)
for i in range(cnt):
print(result[i][0], result[i][1])이제 함수 밖에서 hanoi라는 함수를 호출할 차례이다. 일단 처음에 입력 받는 원판의 갯수를 넣고 출발지를 넣는다. 그리고 1차 도착지를 설정해주고 마지막으로 도착할 위치를 넣는다. 이 과정은 n-1개의 원판이 2번 장대로 이동하기 위한 과정이다.
그리고 앞에서 move를 리스트에 차례대로 추가를 해주었기 때문에 for문을 이용해 출력해주도록 하였다.
최종 코드
n=int(input())
cnt=0
result=list()
def move(n,start, end):
global cnt
result.append([start, end])
cnt+=1
def hanoi(n, start, end, sub):
global cnt
if n==1:
move(1,start, end)
return
else:
hanoi(n-1, start, sub, end)
move(n, start, end)
hanoi(n-1, sub, end, start)
hanoi(n,1, 3, 2)
print(cnt)
for i in range(cnt):
print(result[i][0], result[i][1])초기 입력부분까지 추가한 최종 코드이다.
결론
하노이의 탑 원리는 알았지만 코드로 구현하기가 쉽지 않았다. 그리고 이동하는 코드를 처음에는 원판 번호까지 구현해야 하는 줄 알고 이 부분까지 생각하기도 했다.
재귀를 오랜만에 풀었기 때문에 코드를 짜기가 쉽지는 않았다. 재귀를 공부하기에 하노이탑 문제가 괜찮았다는 생각이 든다. 하노이탑과 관련된 다른 문제, 그리고 다른 재귀 문제도 자주 풀고, 이를 응용해서 하는 DP도 공부해야 겠다.
