프로그래머스 - 하노이의 탑 [Python]

 문제

 

 

 문제 상황

 

- 하노이의 탑을 옮기는 과정을 리스트에 담아 출력한다.

 

 

 

 해결 전략

- 하노이의 탑에서 중요한 것은 시작점, 경유점, 도착점이 바뀐다는 사실과 전체 문제가 부분 문제로 이루어져있다는 사실이다.

 

 

 

 코드

 

# 출발노드, 경유노드, 도착노드, 판의 수
def hanoi(start_node, pass_node, desti_node, n):
    global result
    if n == 1 : 
        return [start_node, desti_node]
    else :    
        result.append(hanoi(start_node, desti_node, pass_node,n-1))
        result.append([start_node, desti_node])
        result.append(hanoi(pass_node,start_node,desti_node,n-1))
 
def solution(n):
    global result
    result = []
    hanoi(1,2,3,n)
    result = list(filter(None, result))
    return result

 

 

 해설

 

- 노드 세종류와 판의 개수를 넣는 함수를 만들었다. 판이 1개일 때에는 바로 출발점에서 도착점으로 가면 되고 그게 아닐 경우는 1부터 n-1개의 판을 경유점에 이동시켜두고, 가장 아래 판을 도착점에 옮긴 후 다시 경유점에서 도착점까지 n-1개의 판을 옮긴다.

 

 

 

 새로 학습한 것 & 실수 

 

- 함수 자체가 return을 기저조건에 넣고 전역변수에 append하는 구조이다보니 None값이 자꾸 담겼다. 결국 None값을 마지막에 제거해주었다. 

 

- 중간에 가장 아래 판을 옮기는 과정(line 8)을 단순하게 [1,3]으로 처리하였었는데 틀렸다. 왜냐하면 부분 문제가 recursive하게 들어갈 때 목적지가 2가 되는 경유도 있으므로 이를 수정해주어 오답을 벗어났다.

 

 

 

 

출처 - https://programmers.co.kr/learn/courses/30/lessons/12946?language=python3