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

[카카오 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 nodes = new ArrayList<>(); int index = 0; public int[][] solution(int[][] nodeinfo) { for (int i=0;i() { 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 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

728x90

from http://white-board.tistory.com/173 by ccl(A) rewrite - 2021-08-16 10:00:53