[백준] 1914 : 하노이 탑

문제

느낀점

이 문제는 먼제 하노이탑이 움직인 횟수를 출력하고 원반의 개수가 20개 이상이면 움직인 기둥이 어떻게 되는지 프린트 해주는 문제이다.

일단 하노이탑을 재귀로 이해하는 데에 가장 중요한 것은 재귀 함수를 하면 재귀가 다 끝나고 리턴이됐을 때 재귀함수를 호출한 곳으로 다시 돌아온다는 것이었다! <= 이 개념이 가장 중요!

그렇게 재귀함수를 호출한 곳으로 불러준 다음, 재귀 루프가 모두 끝나면 그 아래의 코드들이 실행되었다. 그래서 하노이 탑의 경우,

크게 네 부분으로 코드가 나뉘는데,
1. 가장 큰 원반 시작 -> 목표 (만약 원반 한 개만 남았을 때 실행됨 - 실제 움직이는 부분)
2. 가장 큰 원반 제외한 나머지 모든 원반 시작 -> 보조 (재귀 - 1. 실행할 때까지)
3. 가장 큰 원반 시작 -> 목표 (만약 원반 한 개만 남았을 때 실행됨 - 실제 움직이는 부분)
4. 원반 개수 하나 빼고 보조 -> 목표 (재귀 - 1. 실행할 때까지)

또한 좌충우돌을 겪은 부분이 바로 하노이탑이 움직인 횟수를 구하는 것이었다.
그냥 공식이 있다.

2 ** (원반 개수) - 1

이걸 굳이 카운트로 세진 않아도 된다.
카운트 횟수와 움직인 것을 모두 프린트하려고 hanoi 함수의 리턴값 개수를 2개 주니 tuple로 자료형이 되어 에러가 발생했다.

그냥 깔끔하게 리턴값을 하나로 주었다.

하노이 탑 (개념)

파이썬 코드

MOVE_MESSAGE = "{}번 원반을 {}에서 {}로 이동"


def move(N, start, destination):
    print(MOVE_MESSAGE.format(N, start, destination))


def hanoi(n, start, destination, via):
    """
    하노이의 탑 규칙에 따라 원반을 옮기고,
    옮길 때마다 원반의 시작 위치와 이동한 위치를 출력합니다.
    마지막으로 총 이동 횟수를 반환합니다.
    :params
        n: 총 원반 개수
        start: 시작 기둥
        destination: 도착 기둥
        via: 보조 기둥:
    :return count:
    """
    # 원반이 1개일 때 시작 기둥에서 도착 기둥까지 한 번에 이동
    if n <= 1:
        move(1, start, destination)
        return 1

    count = 0
    # 원반 n-1개를 시작 기둥에서 보조 기둥으로 이동
    count += hanoi(n - 1, start, via, destination)

    # 가장 큰 원반을 시작 기둥에서 도착 기둥으로 이동
    count += 1
    move(n, start, destination)

    # 원반 n-1개를 보조 기둥에서 도착 기둥으로 이동
    count += hanoi(n - 1, via, destination, start)

    return count


if __name__ == '__main__':
    n = 3
    start = 1
    destination = 3
    via = 2

    total_count = hanoi(n, start, destination, via)
    print('총 이동 횟수:', total_count)


'''
출력 결과

1번 원반을 1에서 3로 이동
2번 원반을 1에서 2로 이동
1번 원반을 3에서 2로 이동
3번 원반을 1에서 3로 이동
1번 원반을 2에서 1로 이동
2번 원반을 2에서 3로 이동
1번 원반을 1에서 3로 이동
총 이동 횟수: 7
'''

참고 사이트
https://www.acmicpc.net/problem/1914

정답코드

import sys

def move(s,d):
    print(s, d, sep =" ")

def hanoi(n, s, d, v):
    m = '' # 어디에서 어디로 이동했는지 저장
    if n <= 1:
        move(s, d)
        return 1
    
    count = 0
    count += hanoi(n-1, s, v, d) # n-1개를 시작 -> 보조
    
    count += 1 # 가장 큰 원반: 시작 -> 목표
    move(s,d)
    
    count += int(hanoi(n-1, v, d, s)) # n-1개를 보조 -> 목표
    
    return count

n = int(sys.stdin.readline())
s = 1
d = 3
v = 2

print(2**n-1) # 원반이 n개일 때 움직이는 횟수는 2의 n승 -1!

if n <= 20:
    hanoi(n, s, d, v) # 20 이하일 때 하노이 함수를 실행하면 move() 함수에서 알아서 print가 됨!

공식 사용하지 않고 횟수 구하는 법

def m(n):
	if n == 1:
    	return 1 # 마지막 원반은 어디든지 한 번만 움직이면 되므로 1을 리턴해줌
    return 2 * m(n-1) + 1
    # 1을 더해준 건 가장 큰 원반을 처음 -> 끝
    # 2를 곱해준 건 재귀를 실행해주는 게 두 번이어서

리턴값 2개 (튜플) 에러 코드

import sys

def hanoi(n, s, d, v):
    m = '' # 어디에서 어디로 이동했는지 저장
    if n <= 1:
        m += str(s) + " " + str(d) + "\n"
        return 1
    
    count = 0
    count += hanoi(n-1, s, v, d) # n-1개를 시작 -> 보조
    
    count += 1 # 가장 큰 원반: 시작 -> 목표
    m += str(s) + " " + str(d) + "\n"
    
    count += int(hanoi(n-1, v, d, s)) # n-1개를 보조 -> 목표
    
    return m, count

n = int(sys.stdin.readline())
s = 1
d = 3
v = 2

m, count = hanoi(n, s, d, v)
print(count)
print(m)