programmers / 길 찾기 게임 / python

코딩테스트 연습 - 길 찾기 게임

자세한 해설

재귀함수를 활용하여 쉽게 해결할 수 있습니다.

부모노드를 기준으로 노드를 나누고, 나눈 노드들로 재귀함수를 호출하며 순회를 기록하면 됩니다.

 

• programmers에서 채점 할 때 재귀 호출이 많이 깊어지므로 해당 코드가 있어야 런타임 오류가 나지 않습니다.

import sys
sys.setrecursionlimit(10**6)

 

• 부모노드의 x를 기준으로 왼쪽에 갈 노드들과 오른쪽에 갈 노드들을 만들어 줍니다.
  이 과정에서 자연스럽게 부모노드는 포함이 되지 않습니다.

left = [node for node in nodes if node[1] < x]
right = [node for node in nodes if node[1] > x]

 

• 왼쪽 노드들 부터 순회하는 것에 유의합니다.

pre.append(parent)
for nodes in [left, right]:
    if nodes: 
        pre, post = traversal(nodes, pre, post)
post.append(parent)

 

---

전체코드

import sys
sys.setrecursionlimit(10**6)

def solution(nodeinfo):
    nodes = [(i+1, x, y) for i, (x, y) in enumerate(nodeinfo)]
    return traversal(nodes, [], [])

def traversal(nodes, pre, post):
    parent, x, y = sorted(nodes, key=lambda x: x[2])[-1]
    left = [node for node in nodes if node[1] < x]
    right = [node for node in nodes if node[1] > x]
    pre.append(parent)
    for nodes in [left, right]:
        if nodes: 
            pre, post = traversal(nodes, pre, post)
    post.append(parent)
    return pre, post

잡담

트리를 먼저 만든 후에 순회를 돌려고 하니 코드가 많이 복잡해졌고, 트리를 dict 그래프로 만드는 구현 자체도 쉽게 되지 않았습니다. 

힌트를 받아 방향을 틀어서 재귀를 하는 동시에 전위순회와 후위순회를 업데이트하며 다시 푸니 다행이도 구현은 간단하게 되었습니다.

 

---

GitHub - bassyu/PS: ☑️ Problem Solving