(파이썬) 백준 11729번 "하노이 탑 이동 순서"

 

---

# 하노이 탑 원리

 

봉 3개를 각각 왼쪽에서부터 1번 봉, 2번 봉, 3번 봉이라고 하겠습니다.

우리의 목표는 1번 봉에 있는 원판들을 모두 3번 봉으로 옮기는 것입니다.

 

원판이 2개일 때를 살펴봅시다. 원판을 어떻게 움직여야 할까요?

 

1단계) 1번 봉에 있는 원판 하나를 2번 봉으로 옮깁니다.

2단계) 1번 봉에 있는 남은 원판 하나를 3번 봉으로 옮깁니다.

3단계) 2번 봉에 옮겨 놓았던 원판을 3번 봉으로 마저 옮깁니다.

 

이 세 단계가 하노이 탑 문제의 핵심입니다. 원판의 개수가 여기서 더 많아져도 모두 이 세 단계를 따릅니다.

원판이 3개인 경우를 살펴볼까요?

 

 

원판이 3개 이상일 때에도 원판이 2개 있다고 생각해야합니다. 원판이 어떻게 2개냐고요?

 

왼쪽 사진에서 제일 아래에 있는 원판 1개를 원판 B,

그 원판 B 위에 있는 나머지 원판들을 모조리 묶어서 원판 A, 1개라고 생각하세요.

그러고 나면 원판이 2개일 때의 풀이법을 그대로 적용시킬 수 있습니다.

 

1단계) 1번 봉에 있는 원판 A를 2번 봉으로 옮깁니다.

2단계) 1번 봉에 있는 원판 B를 3번 봉으로 옮깁니다.

3단계) 2번 봉에 있는 원판 A를 3번 봉으로 옮깁니다.

 

 

그럼 여기서 의문점이 하나 생깁니다.

" 원판 A는 어찌됐든 원판이 여러 개로 구성되어 있으니 한꺼번에 옮길 수가 없는데, 도대체 어떻게 옮기라는 거지? "

이 의문점을 해결해주는 열쇠가 바로 재귀함수에 있습니다. 이제 실제 코드를 보겠습니다.

 

 

 

 

---

# 풀이 1

def hanoi(n, start, mid, end):
    if n == 1:
        print(start, end) # 원판 이동이 발생했다!
    else:
        hanoi(n-1, start, end, mid)
        print(start, end) # 원판 이동이 발생했다!
        hanoi(n-1, mid, start, end)

n = int(input())
print(2**n - 1)
hanoi(n, 1, 2, 3)

hanoi 함수는 다음 4개의 매개변수를 가지고 있습니다.

- n        : 몇 개의 원판을 옮길 것인가?

- start : 어느 봉에서 옮길 것인가?

- mid   : start 봉과 end 봉을 제외한 나머지 봉

- end   : 어느 봉으로 옮길 것인가?

 

즉 제일 마지막 행에 있는 hanoi(n, 1, 2, 3)의 의미는 이렇습니다.

"n개의 원판을 1번 봉에서 3번 봉으로 옮긴다"

 

print()함수는 '옮긴다'라는 행위가 실현되는 것과 같은 의미로 쓰였습니다. 

 

 

1. n == 1일 경우에는 간단합니다.

원판이 1개이니, 그냥 start 봉에서 end 봉으로 바로 옮겨주면 됩니다.

 

2. n > 1인 경우에는 아까 위에서 살펴보았던 3단계를 실천하면 됩니다.

1단계) 1번(start) 봉에 있는 원판들을 2번(mid) 봉으로 옮긴다. → hanoi(n-1, start, end, mid)

2단계) 1번(start) 봉에 있는 맨 아래 원판을 3번(end) 봉으로 옮긴다. → print(start, end)

3단계) 2번(mid) 봉에 있는 원판들을 3번(end) 봉으로 옮긴다. →  hanoi(n-1, mid, start, end)

 

맨 아래 원판을 옮길 때는 옮기는 원판이 1개니까 바로 옮기는 것이 가능하죠. 그러니까 print()함수를 바로 쓸 수 있습니다.

원판들은 한꺼번에 옮기는 것이 불가능하죠. 원판들의 갯수는 맨 아래 원판을 뺀 나머지 원판들이니까 총 n-1개가 되고, 이 원판들에 대해서 또 다시 hanoi 함수를 실행하면 됩니다.

 

 

 

※ 원판을 옮긴 횟수는 왜 '2 ** n - 1'일까요?

출처 : 나무위키

 

 

 

 

---

# 풀이 2

def hanoi(n, l, r):
    m = 6 - l - r
    if n == 1:
        return f'{l} {r}\n'
    else:
        a = hanoi(n-1, l, m)
        b = f'{l} {r}\n'
        c = hanoi(n-1, m, r)
        return a + b + c

n = int(input())
print(f'{2**n - 1}\n' + hanoi(n, 1, 3))

풀이 1의 코드를 살짝만 수정함으로써 코드의 효율을 높여보겠습니다.

 

먼저 풀이 1에서 hanoi의 매개변수 mid 기억나시나요?

mid 값을 직접 입력받아도 되지만, start 값과 end 값만 있어도 충분히 mid 값을 유추할 수 있습니다.

 

봉 1, 2, 3 중에서 start = 1, end = 3이라면 mid는 2가 됩니다.

즉, 1 + 2 + 3 에서 start값과 end값을 빼고 나면 남는 값이 mid 이므로 아래와 같이 표현할 수 있습니다.

mid = 6 - start - end

 

또, 프로그램 실행 시간을 단축시키는 방법을 생각해봅시다.

풀이 1의 코드를 보면 print() 함수가 매우 자주 실행됩니다. 입출력 함수는 프로그램 실행 시간을 많이 잡아먹는 주요 범인입니다. 따라서, hanoi 함수 안에 들어있는 print() 함수는 없애고, 대신 문자열을 반환하게끔 해봅시다.

그리고, 최종적으로 받아온 문자열 값을 코드의 제일 마지막에 딱 1번 출력하게 하면 프로그램 실행 시간을 많이 단축시킬 수 있습니다. 

 

 

 

 

---

# 답

def hanoi(n, l, r):
    m = 6 - l - r
    if n == 1:
        return f'{l} {r}\n'
    else:
        a = hanoi(n-1, l, m)
        b = f'{l} {r}\n'
        c = hanoi(n-1, m, r)
        return a + b + c

n = int(input())
print(f'{2**n - 1}\n' + hanoi(n, 1, 3))