Python 재귀함수 알고리즘 - 백준 11729 하노이탑

Python 재귀함수 알고리즘 - 백준 11729 하노이탑

www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서

def move(n, start, end):
    if n == 1:
        print(start, end)
        return

    move(n - 1, start, 6 - start - end) # 시작부분에서 저장하는 곳으로 다 옮긴 것
    print(start, end) # 시작부분에서 끝부분으로 이동
    move(n - 1, 6 - start - end, end) # 저장한 곳에서 끝으로 옮긴 것


n = int(input())
print(2 ** n - 1) # 총 옮긴 횟수
move(n, 1, 3) # 1기둥에 쌓인 원반 n개를 3기둥으로 옮김

 

처음엔 이해하는데 조금 어려웠지만,

 

손으로 하나하나씩 그려가면서 하니까 재귀함수에 대해 어느정도 이해한 것 같다.

 

문제에서 요구하는 것은 1기둥에 있는 모든 원판을 3기둥으로 옮기는 과정을 출력하는 것이다.

 

하노이의탑은

 

그 과정을 간략히 말하면

 

맨 밑에있는 제일 큰 원반을 제외하고 나머지 원반을 2번째 기둥에 옮겼다가,

 

맨 밑에 있는 원반을 3번째 기둥에 옮긴 후, 나머지를 모두 3번째 기둥으로 옮기는 방식이다.

 

def move(n, start, end):
    if n == 1:
        print(start, end)
        return

    move(n - 1, start, 6 - start - end) # 시작부분에서 저장하는 곳으로 다 옮긴 것
    print(start, end) # 시작부분에서 끝부분으로 이동
    move(n - 1, 6 - start - end, end) # 저장한 곳에서 끝으로 옮긴 것

함수 move는 (n, start, end)값을 받는다.

n -> 원판 갯수

start -> 시작 기둥

end -> 끝 기둥 (목표 기둥)

 

만약 원판 갯수가 1개밖에 없다면, 옮겨야할 것이 1개밖에 없기 때문에, 마지막으로 옮길 시작지점과 끝지점을 프린터하고, 함수를 끝낸다.

 

이 함수를 좀 이해하기 위해선 재귀함수에 대한 이해가 필요하다.

 

함수는 이렇게 구성되어 있다.

1. 바닥에 있는 원반을 제외한 그룹(원반[1]~원반[no-1])을 1기둥에서 2기둥으로 옮긴다.

2. 옮긴 원반을 출력한다.

3. 바닥에 있는 원반을 제외한 그룹(원반[1]~원반[no-1])을 2기둥에서 3기둥으로 옮긴다.

 

---

대입해서 확인

처음 input값이 3 , 1 , 3 이니, 대입해서 보면

 

move(3,1,3)   0. if 문 -> n이 3이기 떄문에 통과 1. move(2,1,2)     #(n-1, start, 6 - start - end) 2. print(1,3)   # (start,end) 3. move(2,2,3)   #(n-1, 6 - start- end, end)

 

여기서 6을 설정한 이유는 원판이 1,2,3의 숫자를 가지고 3개 있기 때문에, 시작기둥이나 목표기둥이 어디에 있든 중간기둥은 (6 - start - end)로 구할 수 있다.

 

여기서 재귀함수의 특징이 나오는데,

 

move에 3,1,3을 넣었다고 바로 2번의 print가 출력되는 것이 아니라,

 

먼저 1번인 move(2,1,2)를 모두 발동시킨 뒤에 2번 print(1,3)이 출력된다.

 

그럼 2번 print(1,3)이 출력되기전,

 

move(2,1,2)도 똑같이 위와 같이 대입하면

 

move(2,1,2) 0. if문 -> n이 2이기 때문에 통과 1. move(1,1,3)   #(n-1, start,  6-start-end) 2. print(1,2)    #(start,end) 3. move(1,3,2 )  #(n-1, 6 - start- end, end)

똑같이 move(2,12)도 2번의 print를 하기 전 1번 move(1,1,3)을 먼저 실행시키고, move(1,1,3)도 똑같이 위와 같은 순서로 실행된다.

 

즉, 처음 move(3,1,3)에서 print(1,3)이 나오기까지 이런 구성을 가진다.

move(3,1,3)	move(2,1,2)	move(1,1,3)
		print(1,2)
		move(1,3,2)
	print(1,3)
	move(2,2,3)	move(1,2,1)
		print(2,3)
		move(1,1,3)

위에서부터 차례대로 실행된다.

 

함수에서 n값이 1일 경우는 if문을 통하여 바로 print(start, end)를 출력하고 return하며 함수를 끝내기 때문에 탈출조건이 된다.