[프로그래머스] 🎮 길 찾기 게임 - 2019 카카오 블라인드 채용 / Python / KAKAO BLIND RECRUITMENT

[프로그래머스] 🎮 길 찾기 게임 - 2019 카카오 블라인드 채용 / Python / KAKAO BLIND RECRUITMENT

문제 설명

전무로 승진한 라이언은 기분이 너무 좋아 프렌즈를 이끌고 특별 휴가를 가기로 했다.

내친김에 여행 계획까지 구상하던 라이언은 재미있는 게임을 생각해냈고 역시 전무로 승진할만한 인재라고 스스로에게 감탄했다.

라이언이 구상한(그리고 아마도 라이언만 즐거울만한) 게임은, 카카오 프렌즈를 두 팀으로 나누고, 각 팀이 같은 곳을 다른 순서로 방문하도록 해서 먼저 순회를 마친 팀이 승리하는 것이다.

그냥 지도를 주고 게임을 시작하면 재미가 덜해지므로, 라이언은 방문할 곳의 2차원 좌표 값을 구하고 각 장소를 이진트리의 노드가 되도록 구성한 후, 순회 방법을 힌트로 주어 각 팀이 스스로 경로를 찾도록 할 계획이다.

라이언은 아래와 같은 특별한 규칙으로 트리 노드들을 구성한다.

• 트리를 구성하는 모든 노드의 x, y 좌표 값은 정수이다.
• 모든 노드는 서로 다른 x값을 가진다.
• 같은 레벨(level)에 있는 노드는 같은 y 좌표를 가진다.
• 자식 노드의 y 값은 항상 부모 노드보다 작다.
• 임의의 노드 V의 왼쪽 서브 트리(left subtree)에 있는 모든 노드의 x값은 V의 x값보다 작다.
• 임의의 노드 V의 오른쪽 서브 트리(right subtree)에 있는 모든 노드의 x값은 V의 x값보다 크다.

아래 예시를 확인해보자.

라이언의 규칙에 맞게 이진트리의 노드만 좌표 평면에 그리면 다음과 같다. (이진트리의 각 노드에는 1부터 N까지 순서대로 번호가 붙어있다.)

이제, 노드를 잇는 간선(edge)을 모두 그리면 아래와 같은 모양이 된다.

위 이진트리에서 전위 순회(preorder), 후위 순회(postorder)를 한 결과는 다음과 같고, 이것은 각 팀이 방문해야 할 순서를 의미한다.

• 전위 순회 : 7, 4, 6, 9, 1, 8, 5, 2, 3
• 후위 순회 : 9, 6, 5, 8, 1, 4, 3, 2, 7

다행히 두 팀 모두 머리를 모아 분석한 끝에 라이언의 의도를 간신히 알아차렸다.

그러나 여전히 문제는 남아있다. 노드의 수가 예시처럼 적다면 쉽게 해결할 수 있겠지만, 예상대로 라이언은 그렇게 할 생각이 전혀 없었다.

이제 당신이 나설 때가 되었다.

곤경에 빠진 카카오 프렌즈를 위해 이진트리를 구성하는 노드들의 좌표가 담긴 배열 nodeinfo가 매개변수로 주어질 때,

노드들로 구성된 이진트리를 전위 순회, 후위 순회한 결과를 2차원 배열에 순서대로 담아 return 하도록 solution 함수를 완성하자.

제한사항

• nodeinfo는 이진트리를 구성하는 각 노드의 좌표가 1번 노드부터 순서대로 들어있는 2차원 배열이다.
• nodeinfo의 길이는 1 이상 10,000 이하이다.
• nodeinfo[i] 는 i + 1번 노드의 좌표이며, [x축 좌표, y축 좌표] 순으로 들어있다.
• 모든 노드의 좌표 값은 0 이상 100,000 이하인 정수이다.
• 트리의 깊이가 1,000 이하인 경우만 입력으로 주어진다.
• 모든 노드의 좌표는 문제에 주어진 규칙을 따르며, 잘못된 노드 위치가 주어지는 경우는 없다.

😃 나의 코드

import functools
import sys
sys.setrecursionlimit(10**6)

preorder_lst = []
postorder_lst = []

class Tree:
    def __init__(self, x, y, index):
        self.x = x
        self.y = y
        self.index = index
        self.left = self.right = None


def preorder(node):
    preorder_lst.append(node.index)
    if node.left:
        preorder(node.left)
    if node.right:
        preorder(node.right)


def postorder(node):
    if node.left:
        postorder(node.left)
    if node.right:
        postorder(node.right)
    postorder_lst.append(node.index)


def compare(info1, info2):
    if info1[1] != info2[1]:
        return info2[1] - info1[1]
    else:
        return info1[0] - info2[0]


def solution(nodeinfo):
    answer = []
    nodeinfo_with_index = [info + [idx+1] for idx, info in enumerate(nodeinfo)]
    nodeinfo_with_index.sort(key=functools.cmp_to_key(compare))
    root_node = None
    for node in nodeinfo_with_index:
        if not root_node:
            root_node = Tree(node[0], node[1], node[2])
        else:
            x = node[0]
            curr_node = root_node
            while True:
                if x < curr_node.x:
                    if curr_node.left:
                        curr_node = curr_node.left
                        continue
                    else:
                        curr_node.left = Tree(node[0], node[1], node[2])
                        break
                if x > curr_node.x:
                    if curr_node.right:
                        curr_node = curr_node.right
                        continue
                    else:
                        curr_node.right = Tree(node[0], node[1], node[2])
                        break
                break
    preorder(root_node)
    postorder(root_node)
    answer.append(preorder_lst)
    answer.append(postorder_lst)
    return answer

이 문제를 풀면서 여러가지 방법들을 찾아야 했었는데, 일단 처음으로 Tree 클래스를 python에서 만들어 본 기억이 없어서 과거 C언어나 JAVA에서의 구현을 생각해보거나, 인터넷으로 레퍼런스가 될만한 코드를 찾아야했습니다. 하지만, 이진 탐색 트리(Binary Search Tree)를 위한 완전 이진 트리(Complete Binary Tree)에 관한 내용이 대부분이었고, 불완전한 이진트리를 만드는 방법은 개인적으로 더 생각을 해야했습니다.( 마지막 구현 방법에는 딱히 고민할 필요가 없었던 내용이었습니다 ) 전위 순회(preorder)과 후위 순회(postorder)의 경우에도 오랫만에 접한 용어라 나중에 다시 정리를 해서 글을 올리겠습니다.

풀이를 시작해보자면, 이진 트리(Binary Tree)를 위한 클래스인 Tree를 만듭니다. Tree는 property로 left, right, x, y, index를 가지고 있습니다. 그리고 다른 문제들에서도 쓰였던, 미리 정렬 스킬(?)을 여기서도 사용합니다. 정렬 기준은 전체 노드의 이진 트리 탐색때의 순서와 같아야 하기 때문에 레벨의 기준이 되는 y좌표는 내림차순으로 먼저 정렬하고, 좌우 위치의 기준이 되는 x좌표는 오름차순으로 정렬합니다. 미리 정렬을 해놓아야 이후 연산에서 과정이 조금이라도 더 줄어듭니다. 한 번에 두 가지 기준을 가지고 정렬을 해야하기 때문에 functools.cmp_to_key를 이용하여 정렬을 합니다. 해당 라이브러리는 의외로 자주 쓰이는 느낌입니다.

이제 정렬된 Node 후보들을 이진 트리(Binary Tree)의 알맞은 곳에 넣어주는 과정이 필요합니다. 이 과정은 완전 이진 트리의 삽입과정과 매우 유사하게 진행됩니다. 중간 과정의 Tree가 있고 새로운 Node 후보가 들어왔다고 생각해봅시다. 우선 현재 들어가야할 Node를 root_node라고하고 시작합니다. 그리고 Node의 x 즉 Node의 x 좌표와 Node 후보의 x 좌표를 비교하여 Node 후보의 x 좌표가 작다면 현재 들어가야할 Node를 Node.left값으로 크다면 Node.right 값으로 바꿔줍니다. 이렇게 좌, 우를 돌면서 들어가야 할 Node.left 혹은 Node.right가 None이라면 해당 위치에 Node 후보를 삽입합니다. 사실상 이 이진 트리(Binary Tree)를 만드는 것이 이 문제의 최대 고비라고 할 수 있습니다.

다음은 우리가 만든 Tree를 이용하여 전위 순회(preorder)와 후위 순회(postorder)를 구하는 과정입니다. 이 과정은 각 순회별로 어떤 방법으로 진행되는 지만 알면 해당 순회의 코드를 짜는 것은 그다지 어렵지 않기 때문에 각 순회 방법에 대한 설명으로 대체하겠습니다.

전위 순회(preorder)

1. 노드를 방문한다.
2. 왼쪽 서브 트리를 전위 순회한다.
3. 오른쪽 서브 트리를 전위 순회한다.

후위 순회(postorder)

1. 왼쪽 서브 트리를 후위 순회한다.
2. 오른쪽 서브 트리를 후위 순회한다.
3. 노드를 방문한다.

전위 순회(preorder)와 후위 순회(postorder)의 과정을 보면 각 과정 안에 재귀적으로 구현해야 할 부분이 있다는 걸 알 수 있습니다. 그러나 이렇게 재귀로 짜게 되면 특정 테스트 케이스에서 공포의 런타임 에러가 뜨게됩니다. 다른 곳에서 런타임 에러가 난 이유를 찾았지만 알 수 없어서 포기하던 중, 한 글을 보고 이 부분을 해결했습니다. Python에서 recursion depth(재귀의 깊이)는 최대 1000으로 제한이 걸려있습니다. import sys를 한 후, sys.getrecursionlimit()을 출력해보면 1000이 뜨는 것을 통해 확인할 수 있습니다. 해당 문제는 노드의 갯수 범위가 1에서 10000까지이므로 전위 순회(preorder)나 후위 순회(postorder)의 과정에서 재귀 깊이가 제한보다 커질 수 있습니다. 따라서 재귀 깊이 제한을 바꿔주는 sys.setrecursionlimit(10**6)을 통해 재귀 깊이 제한을 바꿔서 순회를 진행하면 문제가 해결됩니다.

오늘 대부분의 시간을 투자한 문제였습니다. 제가 아직 모르는 부분이 많다는 걸 알고, 더 알아갈 수 있는 내용이 많았던 정말 좋았던 문제였습니다.