[프로그래머스] 길 찾기 게임

https://programmers.co.kr/learn/courses/30/lessons/42892

코딩테스트 연습 - 길 찾기 게임

 

dfs 알고리즘을 이용하여 전위 순회와 후위 순회를 구하려고 하였다. dfs 알고리즘을 사용할 수 있도록 부모와 자식 관계를 나타내는 tree 라는 함수를 사용해 dic 을 구성하였다.

 

1. nodeinfo 에 각 번호를 넣고 y 에 대하여 내림차순, 다음으로 x 에 대하여 오름차순으로 정렬하였다.

2. tree 라는 함수는 7 이 root 라면 7 의 y 값보다 한 단계 작은 값은 자식의 y 값이다. 그리고 x 를 기준으로 2개의 배열로 나눈다.

  - 7 (부모) : [[4 (자식), 6, 1, 9, 8, 5], [2 (자식), 3]], dic[7] = [4, 2]

  - 4 (부모) : [[6 (자식), 9], [1 (자식), 8, 5]], dic[4] = [6, 1]

  - 2 (부모) : [[], [3 (자식)]], dic[2] = [3]

  .

  .

  .

3. 만들어진 dic 으로 재귀함수(dfs 알고리즘)를 이용하여 preorder, postorder 를 구한다.

 

import sys
from collections import defaultdict

sys.setrecursionlimit(10**8)
preorder = []
postorder = []

def solution(nodeinfo):
    global preorder
    global postorder
    answer = [preorder, postorder]
    n = len(nodeinfo)
    
    for i in range(n):
        nodeinfo[i].append(i+1)
    
    nodeinfo = sorted(nodeinfo, key = lambda x : (-x[1], x[0]))
    dic = defaultdict(list)
    tree(nodeinfo, dic)
    rf(dic, nodeinfo[0][2])
    postorder.append(nodeinfo[0][2])
    
    return answer

def tree(array, dic):
    if len(array) < 2: 
        return
    else:
        x, y, p = array[0]
        y_ = array[1][1]
        array_left = []
        array_right = []

        for i in range(1, len(array)):
            if y_ == array[i][1]:
                dic[p].append(array[i][2])
            if x > array[i][0]:
                array_left.append(array[i])
            else:
                array_right.append(array[i])
        
        tree(array_left, dic)
        tree(array_right, dic)

def rf(dic, root):
    global preorder
    global postorder
    preorder.append(root)
    
    for i in dic[root]:
        rf(dic, i)
        postorder.append(i)
        
print(solution([[5, 3], [11, 5], [13, 3], [3, 5], [6, 1], [1, 3], [8, 6], [7, 2], [2, 2]])) # [[7, 4, 6, 9, 1, 8, 5, 2, 3], [9, 6, 5, 8, 1, 4, 3, 2, 7]]