[백준] 11729번: 하노이 탑 이동 순서 - Python

링크: https://www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서

 

풀이

 

이 문제는 3개의 장대에 각각 역할? 부여하고 생각해야했다.

 

첫 시작은 1번 장대는 start, 2번 장대는 sㅕpport, 3번 장대는 target으로 두자

 

start 장대에 원판이 n개가 있다고 가정하면 어쨌거나 n-1개의 원판을 support 장대로 옮기고 가장큰(맨아래) 원판을  target 장대로 이동시키면 이 원판은 고정이다.

 

이 상황을 다시 보면 

1번 장대 -> 0개

2번 장대 -> n-1개

3번장대 -> 1개

이 상태이다.

 

이제는 2번 장대를 start로 1번 장대를 support로 생각하고 진행하면

1번 장대 -> n-2개

2번 장대 ->  0개

3번 장대 -> 2개

이렇게 된다.

 

이런 현상을 구현하기 위한 함수를 

hanoi( 원판의 갯수 n, start장대, target장대, support장대 )

이렇게 만들었다고 보자.

 

말로 풀면 지금 start에 n개의 원판이 있는데 이걸 target으로 옮길거야 라는 함수다.

 

1. 근데 만약 원판이(n)이 1이면 바로 타겟으로 가면 된다. 

 

2. 아니라면 위에서 한 것처럼 n-1개를 support트로 보내자

함수로 표현하면

hanoi( n-1, start장대 , support장대 ,target장대 )

 

3. 다 support로 옮겼으면 남아있는 원판이 바로 타겟으로 가면 된다.

 

4. 이젠 위에서 말한 것처럼 n-1개의 원판이 있는 장대를 start로 놓고 위의 과정을 반복하면 된다.

함수로 표현하면

hanoi( n-1, support장대, target장대, start장대)

 

위의 과정을 코드로 표현하면 다음과 같다.

 

구현

import sys
def hanoi(cnt, start, target, support):
    # 1번 과정
    if cnt == 1: 
        result.append([start, target])
        return
        
    #2번 과정
    hanoi(cnt-1,start, support, target)
    
    #3번 과정
    result.append([start, target])
    
    #4번 과정
    hanoi(cnt-1, support, target, start)

input = sys.stdin.readline

n = int(input())
result = []
hanoi(n, 1, 3, 2)

print(len(result))
for i in result:
    print(" ".join(list(map(str, i))))

마무리

• 알고리즘 수업 시간 재귀 파트에서 배웠던 기억이 있어 쉽게 풀 수 있을 것 같았다..
• 하지만 막상 시도해보니 생각보다 만만치 않았던 문제였디...