🐷전동준(Jeon DongJun)

Go with the flow

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

11729번 - 하노이 탑 이동 순서

문제

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

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

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

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

하노이

입력

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

출력

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

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

예제 입력 1

예제 출력 1

해결할 방법을 생각해보자.💡

재귀함수의 대표적인 문제라고 할 수 있는 하노이의 탑이다.

워낙 다른 분들이 잘 정리해놓으신 분들이 많기 때문에, 질 좋은 설명은 구글링 하시는 것을 추천드린다.

우선 원판의 개수를 받아주자.

N = int(input())

그리고 예제 출력을 보면, 총 횟수가 나오고 그 다음에 어디서 어디로 옮겼는지가 나온다. 따라서, 이동하는 데이터들을 미리 받아놓으려고한다. 이동 데이터 리스트의 길이가 총 이동횟수이기 때문이다.

옮기기 전 위치와 옮기려는 위치를 받기 위한 리스트들을 만들어 주자.

start_lst = []
target_lst = []

문제를 보면 총 3개의 장대가 있다. 1번 장대에 쌓여있는 N개의 원판을 3번 장대로 옮기는 것이 목표다. 그렇다면 2번 장대는 원판을 옮기기 위한 보조 장대로 볼 수 있다.

이제 그림을 통해서 구조를 이해해보자.

만약에 1개의 원판을 1번 장대에서 3번장대로 옮겨야하는 경우는 어떨까?

이런 상태일 것이다. 그렇다면 한 번만 3번 장대로 옮기면 끝난다.

이렇게 표현할 수 있다.

시도1 : 1 -> 3

만약에 2개의 원판이라면 어떨까?

이런 상태일 것이다.

시도1 : 1 -> 2

위에 있는 2번 원판이 보조 장대로 옮겨진다.

시도2 : 1 -> 3

그렇다면 1번에 있는 가장 큰 원판인 1번원판이 목표 장대인 3번 장대로 옮겨진다.

시도3 : 2 -> 3

마지막으로 보조장대인 2번장대에 있던 2번 원판이 목표장대인 3번 장대로 옮겨지며 문제가 해결된다.

대강 흘러가는 흐름을 알았으니 코드로 한번 구성해보자.

우리가 작성하려는 함수에는 4개의 파라미터가 들어갈 것이다.

n = 원판의 개수, start = 시작하는 장대, target = 옮기려는(목표하는) 장대, support = 보조 장대

그리고 위에서 만든 변수들을 함수에서 사용하기 위해서 전역변수를 사용해주자.

def hanoi(n, start, target, support):
    global start_lst
    global target_lst

위의 예제처럼 원판이 한개였을 경우에는 어땠나?

바로 시작 장대에서 목표 장대로 한번만 옮겨주면 끝났다.

만약 함수로 표현한다면 hanoi(1, 1, 3, 2) 가 될 수 있을 것이다.

옮기기 시작점과 옮기는 목표점들을 각각 만들어놓은 리스트에 append해주자.

이 경우에는 재귀가 끝나도록 return을 적용시켜줘야한다.

	if n == 1:
        start_lst.append(start)
        target_lst.append(target)
        return

만약에 2인 경우였다면 어땠을까? 함수로 표현한다면 hanoi(2, 1, 3, 2) 로 볼 수 있다.

재귀함수가 들어가야할 타이밍이 여기다.

위에서 보았듯이 2번 원판이 1번 장대에서 보조장대인 2번 장대로 옮겨진다. 3번 장대는 보조 장대로 밀려버리게 된다. 코드로 표현하면 이렇다.

	# 2번 원판, 1 -> 2
    hanoi(n-1, start, support, target)
    # n이 1이므로
    # start_lst == [1]
    # target_lst == [2]

그리고 나서 가장 넓은(큰) 원판인 1번 원판이 이제 옮겨질 차례다. 1번 장대에서 3번장대로 옮겨지므로, 기존에 적혀진 start(1)와 tagret(3)이 append된다.

	# 1번 원판, 1 -> 3
    start_lst.append(start)
    target_lst.append(target)
    # start_lst == [1, 1]
    # target_lst == [2, 3]

가장 큰 1번 원판을 목표 장대인 3번 장대로 옮기는데 성공했다면 이제 우리가 해야할 일은 무엇일까?

바로 보조 장대인 2번 장대에 있는 2번 원판을 목표 장대인 3번 장대로 옮기는 것이다.

여기서도 함수를 사용해주자.

	# 2번 원판, 2 -> 3
    hanoi(n-1, support, target, start)
    # n이 1이므로
    # start_lst == [1, 1, 2]
    # target_lst == [2, 3, 3]

이렇게 되면 총 3번의 횟수로 하노이탑 쌓기가 성공한다.

입력 N이 2인 경우이기 때문에 출력은 다음과 같다.

따라서 이렇게 나오게 하려면 함수를 밖에서 호출해준 후, 리스트에 있는 값들로 출력을 해줘야한다.

리스트의 길이가 총 시행횟수이고, 출발점과 도착점을 zip하여 순서대로 출력해주면 된다.

hanoi(N, 1, 3, 2)
print(len(start_lst))
for i,j in zip(start_lst, target_lst):
    print(i, j)

설명을 잘 못하는 편이라 도움이 될지는 모르겠지만, 3으로 입력값을 넣어보면 예제처럼 잘 출력될 것이다.

그리고, 문제를 풀면서 알게된 점인데 총 이동 횟수는 원판에 수에 따라 규칙이 있더라.

1개 = 1번

2개 = 1번 + 2번(원판 개수가 하나 적은 경우의 횟수보다 1 큰)

3개 = 1번 + 2번 + 4번(원판 개수가 하나 적은 경우의 횟수보다 1 큰)

4개 = 1번 + 2번 + 4번 + 8번

5개 = 1번 + 2번 + 4번 + 8번 + 16번

만약 n이 5일 경우라면

X = (n-4일 경우) + (n-3일 경우) + (n-2일 경우) + (n-1일 경우) + (n일 경우)

(n-4일 경우) = 1
(n-3일 경우) = (n-4일 경우) + (n-4일 경우 + 1) = 1 + 2
(n-2일 경우) = (n-4일 경우) + (n-4일 경우 + 1) + (n-3일 경우 + 1) = 1 + 2 + 4
…

어쨌든 수열이라는 것이다.

def N(n):
    if n == 1:
        return 1
    result = (N(n-1)+1) + N(n-1)
    return result

print(N(3))

코드💻

N = int(input())
start_lst = []
target_lst = []
def hanoi(n, start, target, support):
    global start_lst
    global target_lst
    if n == 1:
        start_lst.append(start)
        target_lst.append(target)
        return
    hanoi(n-1, start, support, target)
    start_lst.append(start)
    target_lst.append(target)
    hanoi(n-1, support, target, start)

hanoi(N, 1, 3, 2)
print(len(start_lst))
for i,j in zip(start_lst, target_lst):
    print(i, j)

해결 로그

문제 푼 날짜	체크
2022-06-19	✔

2022 196
2021 22

맨 위로 이동 ↑