[코딩 테스트 연습(파이썬/Python)] 백준 11729번 _ 하노이 탑 이동 순서

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

11729번: 하노이 탑 이동 순서

[문제]

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

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

이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

아래 그림은 원판이 5개인 경우의 예시이다.

[입력]

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

[출력]

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

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

 

[아이디어]

1) 재귀함수를 작성해 경로를 탐색한다.

2) 전체 이동 횟수는 2^n-1이다.

3) n번째의 이동 = n-1번째의 이동 + "1 3" + n-1번째의 이동이긴 한데,

이동하는 원판의 시작과 끝만 다르다. 이를 이용해야 한다.

 

# 시간 초과
n = int(input())
def switch_front(x):
    a = str.maketrans("23", "32")
    x = list(map(lambda x: x.translate(a), x))
    return x
def switch_back(x):
    a = str.maketrans("12", "21")
    x = list(map(lambda x: x.translate(a), x))
    return x
def answer(n):
    if n ==1:
        return ["1 3"]
    else:
        return switch_front(answer(n-1)) + ["1 3"] + switch_back(answer(n-1))
print(2**n - 1)
for x in answer(n):
    print(x)

경로를 모두 배열에 담아 차례로 출력하려 했다. 로직은 틀린게 없긴한데, 가차없이 시간 초과가 떴다. 그래도 덕분에 maketrans와 translate의 용도를 알게 됐다. 입력 받는 방식도 그렇고, 요구하는 것이 보통 출력인 백준이 적응이 안된다 ㅠ 시간 문제를 해결하기 위해서는, 그냥 바로바로 출력하게 해야하며 문자열을 바꾸는 과정을 다른 방법으로 바꾸어주어야 한다. (다른 사람의 풀이를 참고했다.)

 

def hanoi_tower(n, start, end) :
    if n == 1 :
        print(start, end)
        return  
    hanoi_tower(n-1, start, 6-start-end) # 1단계
    print(start, end) # 2단계
    hanoi_tower(n-1, 6-start-end, end) # 3단계
    
n = int(input())
print(2**n-1)
hanoi_tower(n, 1, 3)

잠깐 생각은 했었는데,, 애초에 이동의 시작과 끝이 되는 원판의 번호를 인자로 던져주면 해결된다. 다만 2번째부터 가운데 무조건 나오는 "1 3"의 이동 앞과 뒤에서, 내가 최종적으로 3에 옮기고 싶다면 이전 이동을 그대로 따라하되 1 -> 3이 아니라 1 -> 2로 이동시켜야하는데, 이를 세 원판의 합이 6이라는 사실을 활용하는 것을 떠올리기가 어려웠다. 

 

좀 인정하기 싫지만 백준 문제들이 더 공부가 많이 되는 것 같긴하다.. 약한 재귀와 기초 알고리즘부터 하나씩 풀어봐야겠다.