[알고리즘/프로그래머스] 길 찾기 게임

프로그래머스 2019 KAKAO BLIND RECRUITMENT 코딩테스트에서 출제된 문제
길 찾기 게임 문제

---

분석

1.트리 만들기

nodeinfo 변수 우선 입력된 순서대로 번호를 부여해준다. 높이인 y값이 기준으로 순서대로 들어가야 구현이 쉬울 것으로 보여서 y값이 큰 순서, 부모부터 구현시켜 나중에 자식이 입력될 수 있도록 정렬을 하였다.

for i in range(len(nodeinfo)): nodeinfo[i] = [i+1] + nodeinfo[i]    
nodeinfo.sort(key=lambda x:(x[2]), reverse=True)
    

트리 구현에서 필요한 노드 class를 정의해주고 트리에 초기 함수와 노드를 연결해주는 insert 함수를 구현한다.

insert 함수는 node가 입력되고 x값을 기준으로 현재 노드의 x값보다 크면 오른쪽 자식으로 작으면 왼쪽 자식으로 이동을 해주고 자식이 없다면 그 부분이 입력된 node의 위치가 될 것이다.

def insert(self, key, x):
        cur_node = self.head
        while True:
            if cur_node.x > x: #left down
                if cur_node.left == None: 
                    cur_node.left = Node(key, x)
                    break
                else: cur_node = cur_node.left
            elif cur_node.x < x: #right down
                if cur_node.right==None: 
                    cur_node.right = Node(key, x)
                    break
                else: cur_node = cur_node.right

---

2.전위 순회, 후위 순회

전위 순회는 발견된 노드를 먼저 출력하고 왼쪽 오른쪽

def preorder(self):
        res = []  
        def order(node):
            nonlocal res
            res.append(node.key)
            if node.left != None: order(node.left)
            if node.right != None: order(node.right)
        order(self.head)
        return res

후위 순회는 왼쪽 오른쪽 노드를 출력하고 발견된 노드를 출력한다.

def postorder(self):
        res = []
        def order(node):
            nonlocal res
            if node.left != None: order(node.left)
            if node.right != None: order(node.right)
            res.append(node.key)
        order(self.head)
        return res

이 개념을 그대로 코드로 작성하였다.

---

3.재귀 함수 문제

테스트 케이스 6, 7이 런타임 에러가 나온다.

import sys
sys.setrecursionlimit(10**6)

python에서 재귀함수의 반복을 제한하는 수치를 올리는 작업을 해주어야 한다.
이 부분은 될 부분인데 되지 않는 것 같아서 검색을 하여서 해결하였다.

---

코드

import sys

sys.setrecursionlimit(10**6)

class Node:
    def __init__(self, key, x):
        self.key = key
        self.x = x
        self.right, self.left = None, None
    
class Tree:
    def __init__(self, head, x):
        self.head = Node(head, x)
        
    def insert(self, key, x):
        cur_node = self.head
        while True:
            if cur_node.x > x: #left down
                if cur_node.left == None: 
                    cur_node.left = Node(key, x)
                    break
                else: cur_node = cur_node.left
            elif cur_node.x < x: #right down
                if cur_node.right==None: 
                    cur_node.right = Node(key, x)
                    break
                else: cur_node = cur_node.right

    def preorder(self):
        res = []  
        def order(node):
            nonlocal res
            res.append(node.key)
            if node.left != None: order(node.left)
            if node.right != None: order(node.right)
        order(self.head)
        return res
        
    def postorder(self):
        res = []
        def order(node):
            nonlocal res
            if node.left != None: order(node.left)
            if node.right != None: order(node.right)
            res.append(node.key)
        order(self.head)
        return res
        
def solution(nodeinfo):
    answer = []
    for i in range(len(nodeinfo)): nodeinfo[i] = [i+1] + nodeinfo[i]      
    nodeinfo.sort(key=lambda x:(x[2]), reverse=True)
    tree = Tree(nodeinfo[0][0], nodeinfo[0][1])
    for i in nodeinfo[1:]: tree.insert(i[0], i[1])    
    answer.append(tree.preorder())
    answer.append(tree.postorder())
    return answer

트리를 구현하는 부분과 순회 알고리즘에 익숙하지 않아서 코드가 많이 지저분해 보인다. 문제를 풀때 다른 풀이 과정을 보면서 푸는 것보다 직접 개념을 코드에서 구현하는 것을 목표로 하였고 직접 구현한 코드가 생각한대로 작동하였고 정답으로 이어졌기 때문에 만족스러웠다.