길 찾기 게임 (42892번) - 프로그래머스 (Programmers)

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

프로그래머스

 

 

프로그래머스 - 길 찾기 게임 (42892번)

 

난이도 : Lv 3

알고리즘&자료구조 : Tree (트리)

 

 

import sys
sys.setrecursionlimit(pow(10, 9))


def solution(nodeinfo):
    def preodr(node):
        if not node:
            return []
        return [node] + preodr(cs[node][0]) + preodr(cs[node][1])
    
    
    def postodr(node):
        if not node:
            return []
        return postodr(cs[node][0]) + postodr(cs[node][1]) + [node]
    
    
    cs = [[0, 0] for _ in range(len(nodeinfo)+1)]
    y_sorted = sorted([(x, y, i) for i, (x, y) in enumerate(nodeinfo, start=1)], key=lambda x: -x[1])
    y_sorted = [i for (_, _, i) in y_sorted]
    nodeinfo = [[]] + nodeinfo
    root = y_sorted[0]
    for i in y_sorted[1:]:
        cur = root
        while True:
            d = 0 if nodeinfo[i][0] < nodeinfo[cur][0] else 1
            if not cs[cur][d]:
                cs[cur][d] = i
                break
            cur = cs[cur][d]
    return [preodr(root), postodr(root)]

 

 

2019 KAKAO BLIND RECRUITMENT 기출문제이다.

주어진 트리 정보를 바탕으로, 전위순회 (pre-order) 와 후위순회 (post-order) 를 구하는 문제이다.

 

---

 

① 먼저 nodeinfo를 y 값 기준 내림차순으로 정렬한 리스트 y_sorted 를 만든다.

y 값이 가장 큰 y_sorted[0] 에 해당하는 노드가, 바로 root 노드이다.

 

 

② 각 노드의 좌우 자식 노드들을 담아줄 cs 리스트를 생성한다.

 

 

③ y_sorted[1] 부터 y_sorted[n-1] 까지 차례대로 방문하면서,

cs 에 트리 정보를 채워나간다.

이 때, x 좌표 정보를 활용한다.

 

현재 방문한 노드가 i 라고 할 때,

루트 노드부터 시작해서

x 좌표가 부모노드의 x 좌표보다 작다면, cs[parent][0] 으로,

x 좌표가 부모노드의 x 좌표보다 크다면, cs[parent][1] 으로,

이동한다.

 

그렇게 이동한 노드의 값이 0이라면

아직 해당 위치에 노드가 없다는 뜻이므로,

현재 노드 i 를 할당해준다.

 

0이 아니라면,

0이 나올때까지 x 좌표 값을 비교하면서 계속 아래로 이동한다.

 

---

 

위와 같이 트리 정보를 모두 cs 에 채워줬다면,

전위 순회와 후위 순회의 정의에 따라서,

root 노드부터 시작해서 전위순회와 후위순회를 만들어서

반환하면 된다.