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

[32] 길 찾기 게임

책 구매하기

문제 정보

• 분류: 트리
• 정답률: 36%
• 권장 시간 복잡도: O(N^2)
• 핵심 키워드: 이진 트리, 좌표, 전위 순회, 후위 순회
• 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/42892

문제를 읽을 때 체크할 포인트

y가 높은 노드가 부모, x가 작은 노드는 왼쪽이라는 규칙만 잡히면 된다. 노드를 y 내림차순으로 보면서 BST처럼 넣고, 마지막에 전위/후위 순회를 하면 요구한 결과가 나온다.

좌표를 그대로 따라가며 트리를 다시 그리는 순간부터 정리가 된다. y가 큰 노드가 위에 오고, x값을 기준으로 왼쪽과 오른쪽이 갈린다고 보면 결국 좌표를 이용해 이진 트리를 복원하는 문제이다.

풀이 흐름

1. 노드 번호와 좌표를 묶어 y 내림차순, x 오름차순으로 정렬한다.
2. 정렬된 순서대로 이진 탐색 트리에 삽입한다.
3. 완성된 트리를 전위 순회, 후위 순회해서 결과를 만든다.

구현할 때 놓치기 쉬운 부분

좌표를 정렬하는 기준과 트리를 구성하는 기준을 섞지 않는 것이 중요하다. y가 큰 노드부터 내려가며 x를 기준으로 왼쪽, 오른쪽을 나누는 흐름이 무너지면 전위 순회와 후위 순회 결과가 모두 틀어진다.

파이썬 정답 코드

import sys

sys.setrecursionlimit(100000)

class Node:
  def __init__(self, x, y, idx):
    self.x = x
    self.y = y
    self.idx = idx
    self.left = None
    self.right = None

def insert(root, node):
  cur = root
  while True:
    if node.x < cur.x:
      if cur.left is None:
        cur.left = node
        return
      cur = cur.left
    else:
      if cur.right is None:
        cur.right = node
        return
      cur = cur.right

def preorder(node, result):
  if node is None:
    return
  result.append(node.idx)
  preorder(node.left, result)
  preorder(node.right, result)

def postorder(node, result):
  if node is None:
    return
  postorder(node.left, result)
  postorder(node.right, result)
  result.append(node.idx)

def solution(nodeinfo):
  # 노드 번호와 좌표를 묶어 y 내림차순, x 오름차순으로 정렬한다.
  nodes = [Node(x, y, idx + 1) for idx, (x, y) in enumerate(nodeinfo)]
  nodes.sort(key=lambda node: (-node.y, node.x))

  root = nodes[0]
  # 정렬된 순서대로 이진 탐색 트리에 삽입한다.
  for node in nodes[1:]:
    insert(root, node)

  # 완성된 트리를 전위 순회, 후위 순회해서 결과를 만든다.
  pre = []
  post = []
  preorder(root, pre)
  postorder(root, post)

  return [pre, post]

시간 복잡도

N은 노드 수이다.

기준 원소마다 다른 원소를 다시 보거나, N×N 형태의 연결 관계를 직접 확인하는 구조이다. 그래서 N이 한 번 더 곱해진 O(N^2)로 정리된다.

따라서 시간 복잡도는 O(N^2)이다.