[프로그래머스] 길 찾기 게임 - Python

🤔 문제

---

 

프로그래머스

 

😀 풀이

---

위 문제는 BST를 구현해본 경험이 있다면 쉽게 풀이할 수 있는 문제입니다. 전체적인 풀이 방향이 BST의 insert, 전위 순회, 후위 순회를 구현하는 문제이기 때문에 이에 대한 내용을 중점적으로 설명해보도록 하겠습니다.

 

먼저 문제에서 y축의 크기가 클수록 BST 상단에 위치해야하므로 아래 코드와 같이 문제에서 주어진 nodeinfo를 정렬해줍니다. 이때 노드의 y값을 기준으로 정렬합니다. y값을 기준으로 정렬하게 되면 순서대로 노드들을 확인했을 때 부모 노드부터 트리에 삽입할 수 있게 되어 문제가 간단해지죠. 또한 정렬하는 과정에서 처음 주어진 인덱스와 순서가 바뀌기 때문에 인덱스 정보도 같이 저장합니다.

    sorted_node_info = [] # 원소 : [idx, x, y]
    
    for idx, [x, y] in enumerate(nodeinfo, 1):
        sorted_node_info.append([idx, x, y]) # 인덱스 정보도 필요하므로 같이 저장
    
    sorted_node_info.sort(key=lambda x: x[2]) # 노드의 y값을 기준으로 정렬

 

그 다음은 노드들을 사용해 트리를 구성해야합니다. 편의를 위해 트리는 dict로 구현하는데 이때 dict의 key값은 노드의 인덱스, value 값은 [(node의x 좌표, node의 y좌표), 왼쪽 자식 인덱스, 오른쪽 자식 인덱스] 의 정보를 담은 배열로 지정해줍니다. 

 

그 후 트리에 root 값을 삽입해주고, 그 후 sorted_node_info 배열을 확인하며 차례대로 insert 함수를 불러 루트에서부터 계속하여 삽입합니다. 해당 부분 코드는 아래와 같습니다.

L, R = 1, 2
    
def insert(tree, node, parent_idx):
    idx, x, y = node
    (p_x, p_y), left, right = tree[parent_idx]
    
    if p_x < x: # 현재 노드 기준 오른쪽으로 삽입되어야하는 노드인 경우
        if right != 0:
            insert(tree, node, right)
        else:
            tree[parent_idx][R] = idx
            tree[idx] = [(x, y), 0, 0]
    
    else: # 현재 노드 기준 왼쪽으로 삽입되어야하는 노드인 경우
        if left != 0:
            insert(tree, node, left)
        else:
            tree[parent_idx][L] = idx
            tree[idx] = [(x, y), 0, 0]
            
 ---------------------------------------------------------------------
 
# 코드 본문 중 일부

tree = dict() # key값으로 [(x, y), left_idx, right_idx]의 정보가 들어갈 것임
root_idx, root_x, root_y = sorted_node_info.pop()
tree[root_idx] = [(root_x, root_y), 0, 0] # 루트 노드 먼저 삽입

while sorted_node_info:
    node = sorted_node_info.pop() # pop하게 되면 y값이 큰 노드부터 나오게 되어 바로 삽입가능
    insert(tree, node, root_idx)

 

위와 같은 과정을 거쳐 insert를 마치게 되면 문제 조건에 맞게 BST가 구성되고, 이제 전위, 후위 순회만 하면 완성입니다!

전위, 후위 순회의 경우 재귀함수를 통해 간단히 구현이 가능하고 해당 코드는 아래와 같습니다.

def pre_order(tree, node_idx): # 전위 순회
    path = []
    
    if node_idx == 0:
        return path
        
    path.append(node_idx)
    path += pre_order(tree, tree[node_idx][L])
    path += pre_order(tree, tree[node_idx][R])
    
    return path


def post_order(tree, node_idx): # 후위 순회
    path = []
    
    if node_idx == 0:
        return path
    
    path += post_order(tree, tree[node_idx][L])
    path += post_order(tree, tree[node_idx][R])
    path.append(node_idx)
    
    return path

---

💻 전체 풀이 코드는 아래와 같습니다.

import sys
sys.setrecursionlimit(10 ** 7)

L, R = 1, 2

def insert(tree, node, parent_idx):
    idx, x, y = node
    (p_x, p_y), left, right = tree[parent_idx]
    if p_x < x:
        if right != 0:
            insert(tree, node, right)
        else:
            tree[parent_idx][R] = idx
            tree[idx] = [(x, y), 0, 0]
    else:
        if left != 0:
            insert(tree, node, left)
        else:
            tree[parent_idx][L] = idx
            tree[idx] = [(x, y), 0, 0]


def pre_order(tree, node_idx):
    path = []
    if node_idx == 0:
        return path
    path.append(node_idx)
    path += pre_order(tree, tree[node_idx][L])
    path += pre_order(tree, tree[node_idx][R])
    return path


def post_order(tree, node_idx):
    path = []
    if node_idx == 0:
        return path
    path += post_order(tree, tree[node_idx][L])
    path += post_order(tree, tree[node_idx][R])
    path.append(node_idx)
    return path


def solution(nodeinfo):
    sorted_node_info = [] # 원소 : [idx, x, y]
    for idx, [x, y] in enumerate(nodeinfo, 1):
        sorted_node_info.append([idx, x, y])
    sorted_node_info.sort(key=lambda x: x[2])

    tree = dict() # [(x, y), left_idx, right_idx]
    root_idx, root_x, root_y = sorted_node_info.pop()
    tree[root_idx] = [(root_x, root_y), 0, 0]

    while sorted_node_info:
        node = sorted_node_info.pop()
        insert(tree, node, root_idx)

    answer = [pre_order(tree, root_idx), post_order(tree, root_idx)]
    return answer