[코딩테스트/백준/Python]하노이 탑 이동 순서

Enter·2021년 8월 17일

코딩테스트

목록 보기

34/68

🔍하노이 탑 이동 순서

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

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

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

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

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

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

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

2021.08.21. 첫번째

💡생각

경로는 생각을 못해서 일단 옮긴 횟수부터 코드 짜려고 원반이 4개일 경우까지 젹어본 뒤 규칙을 찾아 재귀합수로 작성함.

❓잘못된 코드1

옮긴 횟수는 재귀함수를 이용해서 금방 구할 수 있었는데 (1, 3(1+2), 7(1+2+4),15(1+2+4+8) .... (2^0+2^1+ ... + 2^N-1) = 1번째, 2번째, 3번째, 4번째....N번째 옮긴 횟수) 이동순서를 구하기 어려워서 이동순서는 다른 사람의 코드를 보기로 하였다.

N = int(input())

def Hanoi(n):
  if n >= 2:
    n = 2 ** (n-1) + Hanoi(n-1)
  elif n == 1:
    return 1

  return n
  

def solution(num):
  print(Hanoi(num))

solution(N)

2022.08.10. 두번째

💡생각

옮긴 횟수랑 경로를 함께 써야 한다는 것은 알고 있었지만 코드를 어떻게 작성해야할지 몰라서 다른사람의 코드를 봄.
다른사람의 코드를 확실히 이해한 뒤 다음번에 풀 수 있도록 외워야 할 것 같음.

⏬다른사람의 코드

생각보다 코드가 간단했고 옮긴 횟수랑 경로를 함께 같은 함수에 써줘야 함. 나는 처음에 옮긴 횟수랑 경로를 다른 함수에 써야한다고 생각했는데 그게 문제였던 것 같음.

🔗풀이 참고
https://leedakyeong.tistory.com/m/entry/%EB%B0%B1%EC%A4%80-python-11729%EB%B2%88-%ED%95%98%EB%85%B8%EC%9D%B4-%ED%83%91-%EC%9D%B4%EB%8F%99-%EC%88%9C%EC%84%9Chanoi-top-in-python

def hanoi(n,a,b,c):
   if n==1:
      move.append([a,c])
   else:
      hanoi(n-1,a,c,b)
      move.append([a,c])
      hanoi(n-1,b,a,c)
      
move = [] # 이동 경로를 담을 list 
hanoi(int(input()),1,2,3) # function 실행

print(len(move)) # 이동 횟수
print("\n".join([' '.join(str(i) for i in row) for row in move])) # 이동 경로 출력