[Baekjoon 1914 / python / 실버1] 하노이 탑

n = int(input())

def hanoi(no, start, end, mid): # no번 원반을 start에서 end로 옮긴다

    if no == 1: # 원반이 1개라면 위에 방해되는 원반이 없으니 즉시 옮긴다

        print(start, end)

        return

   

    else:

        hanoi(no-1, start, mid, end) # 2개 이상이면 위에 방해되는 원반을 치운다

        print(start, end) # 방해되는거 치웠으니 원래 옮기려던거 목표자리에 옮긴다

        hanoi(no-1, mid, end, start) # 치워둔것도 목표자리에 옮긴다

if n <= 20:

    print(2 ** n - 1) # 최소횟수 출력

    hanoi(n, 1, 3, 2) # 경로 출력

else:

    print(2 ** n - 1) # 경로 출력 안해도 되니 최소횟수만 출력

 

정말 아주, 매우 끔찍한 문제였다.

 

5시간동안 하노이 탑 알고리즘에 대해 쳐다보고 검색하고 찾아본 결과 겨우겨우 원리를 이해할 수 있었다.

그리고 남은 1시간동안 코드를 짜서 제출했다.

하노이 탑에 대해 쉽게 설명되어 있는 글이 없더라.. 아니 애초에 쉽게 설명하기 힘들 것 같다.

 

def hanoi(no, start, end, mid) 

원반갯수, 출발지, 도착지, 경유지 순서다. 매개변수 이름은 신경 안 쓰는게 이해하기 편하다.

그냥 4개 순서대로 원반갯수, 출발지, 도착지, 경유지 라는 것만 인지하자.

"no번 원반을, start에서 end로 보낸다" 라고 생각하고 이해해라. 그리고 경유지(mid)는 너무 신경쓰지 마라. 그냥 출발지, 도착지가 있고 남은 1곳이 경유지다 정도로 생각하자.

 

재귀함수가 사용되는 문제이다. 주석을 최대한 간단하고 이해하기 쉽게 달아 놓았으니, 하노이 탑 알고리즘 원리를 다른 곳에서 좀 이해한 후 내 코드를 보면 이해하기 수월할 거라 믿는다.