재귀 (Recursion) 함수

컴퓨터 과학에 있어서 재귀는 자신을 정의할 때 자기 자신을 재참조하는 방법을 뜻합니다.

백준 알고리즘: #11729 하노이 탑 이동 순서

이 문제는 solved.ac에서 silver2단계로 마크되어 있습니다.

문제

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.

한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다. 아래 그림은 원판이 5개인 경우의 예시이다.

입력

첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 <= N <= 20)이 주어진다.

출력

첫째 줄에 옮긴 횟수 K를 출력한다.

두 번째 줄에서 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.

풀이

하노이 탑 문제를 해결하기 위한 재귀 과정을 생각해 봅니다.

def hanoi(n, start = 1, by = 2, to = 3):    # 항상 장대가 3개이고 1 -> 3이 목표임
    if n == 1:                                # 따라서 default값 설정함
        move(start, to)                        # 원반이 1개 남고 함수가 끝난다
    else:
        hanoi(n - 1, start, to, by)            # n-1개의 원반을 2번째 장대에 두고
        move(start, to)                        # 나머지 하나를 3번째 장대에 옮긴다
        hanoi(n - 1, by, start, to)            # n-1개의 원반을 3번째 장대에 옮긴다

이 문제는 n개의 원반이 입력된 하노이 탑 문제를 n - 1, n - 2, ..., 1개의 원반을 옮기는 문제로 점점 줄여가면서 풀 수 있습니다.

자기 자신(hanoi())뿐만 아니라 move()라는 실제로 원반을 옮기는 함수가 하나 더 필요하기 때문에, 저 역시 처음부터 효율적인 코드를 짜기는 어려웠습니다.

구글링을 하면서도 직관적인 것이 장점이라는 말이 무색해질 정도로 한 눈에 들어오지도 않았던 것 같아 이번 포스팅을 계기로 확실히 공부하게 되었습니다.

위 그림은 n이 3일 경우에 하노이의 탑이 어떻게 재귀적으로 구현 가능한지 나타냅니다.

hanoi(3)를 호출하면 1번째 장대에 크기순으로 3개가 쌓인 초기 상태가 됩니다.
- 이 때, hanoi() 함수의 start,by,to 인자는 default값으로 자동처리해도 됩니다.
- 어차피 출발은 1장대고 도착은 3장대이기 때문입니다. by인자는 출발과 도착을 제외한 다른 숫자를 넣어주는 거라고 생각하면 됩니다.
hanoi(3)을 호출하면 n이 1이 아니기 때문에 else문으로 갑니다. 여기서 hanoi(2, 1, 3, 2)의 자기 자신을 호출하게 되는데, 제일 큰 원반을 제외한 나머지 2개의 원반을 1번째 장대에서 2번째 장대로 옮긴다는 뜻입니다.
- 이 부분에서 원반 1개씩 옮기지 않는 것은 큰 틀을 보기 위해서입니다! 실제로 hanoi(2, 1, 3, 2)를 호출할 경우 다시 자기 자신이 호출되며 결국 원반을 1개씩 옮기는 단계로 내려갑니다.
다음 줄에 호출되는 move(1, 3)은 1번째 장대에 남아있는 가장 큰 원반을 3번째 장대(목표)로 옮깁니다.
마지막으로 hanoi(2, 2, 1, 3)을 호출하여 아까 2번째 장대에 옮겨놓았던 2개의 원반을 3번째 장대(목표)로 옮길 수 있습니다.

이러한 순서를 통해 결국 hanoi(1, ...)이 호출될 경우, 원반 하나를 1번째 장대에서 3번째 장대로 옮기고 재귀가 끝이 나게 됩니다.

또한 이 문제에서 고려해야 할 것은 출력값입니다.

하노이의 탑을 해결한 이후에 이것이 최소 몇 회의 이동이 일어나는지를 첫 번째 줄에 출력해준 다음, 그 과정을 정해진 형식에 맞춰 순서대로 출력해야 합니다.

따라서 저는 move()함수를 다음과 같이 구성해 보았습니다.

result = []
def move(start, to):
    result.append((start, to))            # tuple 형식으로 저장

move()함수를 호출할 때마다 바로바로 과정을 출력해주면 편하겠지만, 출력 순서가 지정되어 있으므로 전역 공간에 빈 리스트인 result를 선언해줍니다.
move()함수의 인자로 받는 출발지와 목적지를 tuple형식으로 묶어 result에 추가합니다.
- 리스트(List)는 순서가 있는 자료구조이므로 추가된 순서대로 저장이 됩니다. (list.append()함수는 list에 요소를 추가할 때 사용하는 빌트인 함수입니다.)

이렇게 hanoi()를 호출한 이후에 result에 움직인 과정을 넣고, len(result)(이동과정 횟수)와 result의 요소를 한 개씩 출력해 주면 문제가 해결됩니다.

전체 코드

result = []                        # 결과값 저장할 빈 리스트 생성

def move(st, to):
    result.append((st, to))

def hanoi(n, st = 1, by = 2, to = 3):
    if n == 1:                    # base case (재귀 종료 조건)
        move(st, to)
    else:
        hanoi(n - 1, st, to, by)
        move(st, to)
        hanoi(n - 1, by, st, to)

N = int(input())                # N을 정수로 받아옴
hanoi(N)
print(len(result))                # 이동 횟수 출력
for x in result:
    print(x[0], x[1])            # 요소가 2개인 tuple이므로 indexing하여 숫자만 출력

사담

생각보다 메모리나 시간면에서 매우 비효율적으로 보여 맞았지만 조금 슬펐습니다.

최적화할 수 있는 방안이 있을지 찾아봐야겠다는 생각과 동시에 파이썬이라 그런게 아닐까라는 합리화를 조금 했습니다..😃😃