문제

프로그래머스 길 찾기 게임

문제풀이

재귀함수를 적절히 구현할 수 있느냐를 측정할 수 있는 문제인 것 같다.

문제를 해결하기 위한 과정은 다음과 같다.

1. 주어진 노드를 binary tree에 넣기 위한 형태로 정렬
2. 문제에서 주어진 조건을 사용하여 binary tree 구현
3. 전위(preorder), 후위(postorder) 순회

여기서 중요한 것은 2번 과정인 binary tree를 어떻게 잘 구현하는가이다.

처음엔 바텀 업 방식으로, 자식노드에서 시작해 부모노드를 타고 올라가면서 조건에 맞는지 확인하는 방식으로 코드를 구현했다. 하지만 이 방식은 문제에서 주어진 조건만 만족하면 노드의 위치가 정해지는 deterministic한 방법이 아니라 조건에 맞는 부모노드를 찾을때까지 여러 노드를 찾아다녀야하는 방식이라 $O(nlogn)$으로 비효율적이었다.

그래서 부모노드부터 시작해서 조건에 맞으면 자식노드를 해당 부모노드 밑에 추가하는 방식으로 방식을 바꿨다. 이 방법은 deterministic하게 노드의 위치가 정해지기 때문에 $O(logn)$만에 자식노드의 위치를 확정할 수 있다.

binary tree를 제대로 구현하기만 하면 tree를 순회하는 것은 dfs로 간단하게 구현할 수 있다.

# 풀이 1
import sys
sys.setrecursionlimit(10**6)
import heapq

def solution(nodeinfo):
    answer = []
    def make_binary_tree(parent, child):
        if parent[1] > child[1]:
            if tree[parent[2]][0]:
                make_binary_tree(tree[parent[2]][0], child)
            else:
                tree[parent[2]][0] = child
        else:
            if tree[parent[2]][1]:
                make_binary_tree(tree[parent[2]][1], child)
            else:
                tree[parent[2]][1] = child

    def dfs(x):
        preorder.append(x)
        if tree[x] == [0, 0]:
            postorder.append(x)
        else:
            for nxt_node in tree[x]:
                if nxt_node != 0:
                    dfs(nxt_node[2])
            postorder.append(x)
    # 1. init settings
    N = len(nodeinfo)
    max_heap = []
    tree = {}
    
    for i in range(N):
        # [y, x, node_number]
        heapq.heappush(max_heap, [-nodeinfo[i][1], nodeinfo[i][0], i+1])
        tree[i+1] = [0,0]

    root = heapq.heappop(max_heap)

    # 2. set binary tree for preorder, postorder
    while max_heap:
        child = heapq.heappop(max_heap)
        make_binary_tree(root, child)
        
    # 3. traverse by preorder, postorder
    preorder = []
    postorder = []
    dfs(root[2])

    answer.append(preorder)
    answer.append(postorder)
    return answer

# 풀이 2
import heapq

class Node:
    def __init__(self, x, data) -> None:
        self.data = data
        self.x = x
        
class TreeNode:
    def __init__(self, node) -> None:
        self.root = node
        self.left = None
        self.right = None

class BinaryTree:
    def __init__(self) -> None:
        self.head = None
        self.preorder = []
        self.postorder = []

    def push(self, data_node):
        cur = self.head
        node = TreeNode(data_node)
        if cur == None:
            self.head = node
        else:
            while True:
                if node.root.x < cur.root.x:
                    if cur.left:
                        cur = cur.left
                    else:
                        cur.left = node
                        break
                else:
                    if cur.right:
                        cur = cur.right
                    else:
                        cur.right = node
                        break

    def traverse(self, x):
        self.preorder.append(x.root.data)
        if x.left:
            self.traverse(x.left)
        if x.right:
            self.traverse(x.right)
        self.postorder.append(x.root.data)
    

def solution(nodeinfo):
    answer = []
    
    # 1. init settings
    N = len(nodeinfo)
    max_heap = []
    tree = BinaryTree()
    
    for i in range(N):
        # [y, x, node_number]
        heapq.heappush(max_heap, [-nodeinfo[i][1], nodeinfo[i][0], i+1])

    # 2. set binary tree for preorder, postorder
    while max_heap:
        y, x, node = heapq.heappop(max_heap)
        tree.push(Node(x, node))
        
    # 3. traverse by preorder, postorder
    tree.traverse(tree.head)

    answer.append(tree.preorder)
    answer.append(tree.postorder)
    return answer


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]]

tree를 구현하는 건 bottom-up보다 top-down 방식이 좋은 것 같다. 풀이 1은 class를 사용하지 않고 구현하고 싶어서 list를 사용하는 방식으로 tree를 구현했지만, 확실히 이 방법은 가독성이 많이 떨어져 코드를 짤 때도 계속 헷갈렸었다. 다음부턴 그냥 마음 편하게 class로 구현해야겠다.