[1스4코1파] #102. LV 2. 하노이의 탑

gunny·2023년 4월 15일

1스4코1파 코딩테스트 코딩테스트 python 프로그래머스 하노이의 탑 프로그래머스 하노이의 탑 python

코딩테스트

목록 보기

102/530

[1스4코1파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 1명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (102일차)
[4코1파] 2023.01.13~ (93일차)
[1스4코1파] 2023.04.12~ (4일차)

Today :

2023.04.15 [102일차]

프로그래머스 LV 2
하노이의 탑
https://school.programmers.co.kr/learn/courses/30/lessons/12946?language=python3

문제 설명

하노이 탑(Tower of Hanoi)은 퍼즐의 일종입니다. 세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있습니다. 게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것입니다.
한 번에 하나의 원판만 옮길 수 있습니다.
큰 원판이 작은 원판 위에 있어서는 안됩니다.
하노이 탑의 세 개의 기둥을 왼쪽 부터 1번, 2번, 3번이라고 하겠습니다. 1번에는 n개의 원판이 있고 이 n개의 원판을 3번 원판으로 최소 횟수로 옮기려고 합니다.
1번 기둥에 있는 원판의 개수 n이 매개변수로 주어질 때, n개의 원판을 3번 원판으로 최소로 옮기는 방법을 return하는 solution를 완성해주세요.

제한사항

n은 15이하의 자연수 입니다.

입출력 예

입출력 예 설명

입출력 예 #1
다음과 같이 옮길 수 있습니다.

문제 풀이 방법

이런 괴상한 문제.. 하노이의 탑은 재귀를 이용해야 하는데
예를 들어서 주어진 n은
(1) n-1개의 원판을 첫번째 기둥에서 두번째 기둥으로 이동
(2) n번째 원판은 첫번째 기둥에서 세번째 기둥으로 이동
(3) n-1개의 원판을 다시 두번째 기둥에서 세번째 기둥으로 옮긴다

이걸 재귀함수로 풀어내면 되는데, 인자는 첫번째, 중간, 세번째 인자에 원판 개수 이다. 와...
종료 조건은 n이 1일 때이고, 이동 순서의 첫 번째와 세번째 기둥을 리스트에 삽입하면 됨..

이.. 이게 뭐야..

참고한 곳들

내 코드

def solution(n):
    answer = []
    
    def get_hanoi(start, end, mid, n):
        if n == 1:
            answer.append([start, end])
        else:
            get_hanoi(start,mid,end,n-1)
            get_hanoi(start,end,mid,1)
            get_hanoi(mid,end,start,n-1)
            
    get_hanoi(1,3,2,n)
    
    return answer

증빙