[프로그래머스] Lv.3 길 찾기 게임 [Python, 파이썬] KAKAO

• 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/42892
• 🔑 DFS) 왼쪽 트리, 오른쪽 트리를 나누자
  • 사전 작업 : 노드 번호가 없기 때문에 노드 번호를 추가, y값 기준 내림차순 정렬
  • 순회 함수 진입
  • 부모 노드의 x 값 보다 자식 노드의 x 값이 작으면 left 리스트에 추가
  • 반대면 right 리스트에 추가해서 왼쪽, 오른쪽 트리를 구분
  • 전위는 재귀 들어가기 전에 부모 노드의 번호를 저장
  • 후위는 재귀 나오고 나서 부모 노드의 번호를 저장
  • left 리스트에 노드가 있으면 left 리스트를 가지고 재귀 진행
  • 가지고간 left 리스트에 대해서도 left, right 리스트로 나눈다
  • left 리스트에 노드가 없으면 right 리스트로 재귀 진행
  • 위 과정 반복
  • 테스트 케이스 전위 순회 함수 진행 순서
  • parent = [8,6,7]
    left = [ [3,5,4], [5,3,1], [1,3,6], [7,2,8], [2,2,9], [6,1,5] ]
    right = [ [11,5,2], [13,3,3] ]
    preorder_list = [ 7 ]
    
    parent = [3,5,4]
    left = [ [1,3,6], [2,2,9] ]
    right = [ [5,3,1], [7,2,8], [6,1,5] ]
    preorder_list = [ 7, 4 ]
    
    parent = [1,3,6]
    left = [  ]
    right = [ [2,2,9] ]
    preorder_list = [ 7, 4, 6 ]
    
    parent = [2,2,9]
    left = [  ]
    right = [  ]
    preorder_list = [ 7, 4, 6, 9 ]
    
    parent = [5,3,1]
    left = [  ]
    right = [ [7,2,8], [6,1,5] ]
    preorder_list = [ 7, 4, 6, 9, 1 ]
    
    parent = [7,2,8]
    left = [ [6,1,5] ]
    right = [  ]
    preorder_list = [ 7, 4, 6, 9, 1, 8 ]
    
    parent = [6,1,5]
    left = [  ]
    right = [  ]
    preorder_list = [ 7, 4, 6, 9, 1, 8, 5 ]
    
    parent = [11,5,2]
    left = [  ]
    right = [ 13,3,3 ]
    preorder_list = [ 7, 4, 6, 9, 1, 8, 5, 2 ]
    
    parent = [13,3,3]
    left = [  ]
    right = [  ]
    preorder_list = [ 7, 4, 6, 9, 1, 8, 5, 2, 3 ]
    

 

 

import sys
sys.setrecursionlimit(10**6)

def preorder(nodeinfo, preorder_list):     # 전위 순회
    parent = nodeinfo[0]    # 부모 노드
    left, right = [], []
    
    for i in range(1, len(nodeinfo)):
        if parent[0] > nodeinfo[i][0]:  # 부모 x 값 보다 자식 x 값이 작으면
            left.append(nodeinfo[i])    # 왼쪽 트리에 추가
        else:                           # 부모 x 값 보다 자식 y 값이 크면
            right.append(nodeinfo[i])   # 오른쪽 트리에 추가
    
    preorder_list.append(parent[2])     # 노드 번호를 먼저 추가

    if left:                            # 왼쪽 트리가 있으면
        preorder(left, preorder_list)   # 왼쪽 트리로 들어간다
    if right:                           # 왼쪽 트리가 끝나고 오른쪽 트리가 있으면
        preorder(right, preorder_list)  # 오른쪽 트리로 들어간다
    

def postorder(nodeinfo, postorder_list):    # 후위 순회
    parent = nodeinfo[0]    # 부모 노드
    left, right = [], []
    
    for i in range(1, len(nodeinfo)):
        if parent[0] > nodeinfo[i][0]:  
            left.append(nodeinfo[i])    
        else:                           
            right.append(nodeinfo[i])
    
    if left:
        postorder(left, postorder_list)
    if right:
        postorder(right, postorder_list)
        
    postorder_list.append(parent[2])     # 노드 번호를 나중에 추가

def solution(nodeinfo):
    
    for i in range(len(nodeinfo)):      # 노드 번호 입력
        nodeinfo[i].append(i+1)
        
    nodeinfo.sort(key=lambda x : (x[1], x[0]), reverse=True)    # y 값 내림차순 정렬   
    preorder_list = []      # 전위 순회 결과 리스트
    postorder_list = []     # 후위 순회 결과 리스트
    
    preorder(nodeinfo, preorder_list)
    postorder(nodeinfo, postorder_list)
    
    return [preorder_list, postorder_list]