[카카오 2019 공채] 길 찾기 게임

2019년 카카오 공채 길 찾기 게임 해설입니다

---

트리를 구성하고 전위 순회와 후위 순회의 결과를 반환하는 문제입니다. 전위, 중위, 후위 순회는 기초적인 트리 순회 방법이기 때문에 모르시는 분들은 찾아서 공부하셔야 합니다.

이 문제의 핵심은 정렬 그리고 트리 노드 추가입니다.

• 정렬을 통해 트리의 루트를 구하고 노드의 Level에 맞게 왼쪽, 오른쪽 자식 노드를 추가할 수 있습니다.
  • 따라서 배열을 y 좌표에 따라 내림 차순으로 정렬합니다
  • y 좌표의 값이 같을 경우, x 좌표에 따라 오름 차순으로 정렬합니다.
• 부모와 자손 노드의 x 좌표 값을 비교합니다
  • 부모의 x 좌표가 더 클 경우 자손 노드는 부모의 왼쪽 서브트리의 노드 중 하나입니다.
    • 부모의 왼쪽 자식 노드가 없을 경우 자손 노드는 부모의 왼쪽 자식 노드가 됩니다.
    • 이미 존재할 경우 부모의 왼쪽 자식을 다시 부모로하여 재귀적으로 반복합니다.
  • 부모의 x 좌표가 더 작을 경우 자손 노드는 부모의 오른쪽 서브트리의 노드 중 하나입니다.
    • 부모의 오른쪽 자식 노드가 없을 경우 자손 노드는 부모의 오른쪽 자식 노드가 됩니다.
    • 이미 존재할 경우 부모의 오른쪽 자식을 다시 부모로하여 재귀적으로 반복합니다.

Java

import java.util.*;
class Solution {
    static class Node {
        int x, y, value;
        Node left, right;

        Node(int x, int y, int value) {
            this.x = x;
            this.y = y;
            this.value = value;
        }
    }

    List<Node> nodes = new ArrayList<>();
    int index = 0;
    public int[][] solution(int[][] nodeinfo) {

        for (int i=0;i<nodeinfo.length;i++) {
            int[] info = nodeinfo[i];
            nodes.add(new Node(info[0], info[1], i + 1));
        }

        Collections.sort(nodes, new Comparator<>() {
            public int compare(Node n1, Node n2) {
                if (n1.y != n2.y) {
                    return n2.y - n1.y;
                }
                return n1.x - n2.x;
            }
        });

        for (int i=1;i<nodes.size();i++) {
            addNode(nodes.get(0), nodes.get(i));
        }

        int[][] answer = new int[2][nodes.size()];
        preorder(answer[0], nodes.get(0));
        index = 0;
        postorder(answer[1], nodes.get(0));
        return answer;
    }

    public void preorder(int[] result, Node node) {
        if (node != null) {
            result[index++] = node.value;
            preorder(result, node.left);
            preorder(result, node.right);
        }
    }

    public void postorder(int[] result, Node node) {
        if (node != null) {
            postorder(result, node.left);
            postorder(result, node.right);
            result[index++] = node.value;
        }
    }

    public void addNode(Node parent, Node child) {
        if (parent.x > child.x) {
            if (parent.left == null){
                parent.left = child;
                return;
            }
            addNode(parent.left, child);

        } else {
            if (parent.right == null) {
                parent.right = child;
                return;
            }
            addNode(parent.right, child);
        }
    }
}

Python

from sys import setrecursionlimit
setrecursionlimit(10 ** 9)
class Node:
    def __init__(self, value, x, y, left = None, right = None):
        self.value = value
        self.left = left
        self.right = right
        self.x = x
        self.y = y

    def __str__(self):
        return f'value = {self.value}, x = {self.x}, y = {self.y}'

index = 0
def solution(nodeinfo):
    global index
    nodes = [Node(index, info[0], info[1]) for index, info in enumerate(nodeinfo, 1)]    
    nodes.sort(key=lambda n: [-n.y, n.x])

    root = nodes[0]
    for i in range(1, len(nodes)):
        addNode(root, nodes[i])

    answer = [[0 for _ in range(len(nodes))] for _ in range(2)]
    preorder(answer[0], root)
    index = 0
    postorder(answer[1], root)
    return answer

def preorder(seq, node):
    global index
    if node is not None:
        seq[index] = node.value
        index += 1
        preorder(seq, node.left)
        preorder(seq, node.right)


def postorder(seq, node):
    global index
    if node is not None:
        postorder(seq, node.left)
        postorder(seq, node.right)
        seq[index] = node.value
        index += 1

def addNode(parent, child):
    if parent.x > child.x:
        if parent.left is None:
            parent.left = child
            return
        addNode(parent.left, child)
        return
    else:
        if parent.right is None:
            parent.right = child
            return
        addNode(parent.right, child)
        return