코딩 테스트 합격자되기 | 09. 트리

Python 코딩 테스트 학습 기록

트리는 부모와 자식의 연결을 표현하는 자료구조다. 이번 글에서는 프로그래머스 문제를 통해 부모 추적, 순회, BFS, 상태별 탐색을 정리한다.

예상 대진표

프로그래머스 공식 문제 페이지

한 라운드가 끝나면 참가 번호 x는 (x + 1) // 2가 된다. 두 참가자의 다음 라운드 번호가 같아지는 순간이 만나는 라운드다.

def solution(n, a, b):
    round_count = 0

    while a != b:
        a = (a + 1) // 2
        b = (b + 1) // 2
        round_count += 1

    return round_count

홀수 번호는 올림, 짝수 번호는 반으로 줄어들어야 하므로 일반 나눗셈이 아니라 (x + 1) // 2를 쓴다. 예를 들어 3번과 4번은 둘 다 다음 라운드에서 2번이 된다.

다단계 칫솔 판매

프로그래머스 공식 문제 페이지

각 판매자와 추천인의 관계를 부모 딕셔너리로 만들고, 판매 수익을 현재 판매자부터 최상단까지 위로 전달한다.

def solution(enroll, referral, seller, amount):
    parent = dict(zip(enroll, referral))
    profit = {name: 0 for name in enroll}

    for name, count in zip(seller, amount):
        money = count * 100
        current = name

        while current != "-" and money > 0:
            commission = money // 10
            profit[current] += money - commission
            current = parent[current]
            money = commission

    return [profit[name] for name in enroll]

zip(enroll, referral)은 판매자와 추천인을 같은 위치끼리 묶는다. money // 10은 위로 전달할 10%이고, 나머지는 현재 사람의 수익이다. 전달할 금액이 0원이 되면 더 올라가도 변화가 없으므로 반복을 멈춘다.

미로 탈출

프로그래머스 공식 문제 페이지

출발점에서 레버를 먼저 찾고, 레버에서 출구까지 가야 한다. 두 구간 모두 최단거리이므로 BFS를 두 번 실행하면 흐름이 분명하다.

from collections import deque

def bfs(maps, start, target):
    height, width = len(maps), len(maps[0])
    queue = deque([(start[0], start[1], 0)])
    visited = {start}
    dy = [-1, 1, 0, 0]
    dx = [0, 0, -1, 1]

    while queue:
        y, x, distance = queue.popleft()
        if (y, x) == target:
            return distance

        for direction in range(4):
            ny, nx = y + dy[direction], x + dx[direction]
            if 0 <= ny < height and 0 <= nx < width:
                if maps[ny][nx] != "X" and (ny, nx) not in visited:
                    visited.add((ny, nx))
                    queue.append((ny, nx, distance + 1))

    return -1

def solution(maps):
    positions = {}
    for y, row in enumerate(maps):
        for x, value in enumerate(row):
            if value in "SLE":
                positions[value] = (y, x)

    first = bfs(maps, positions["S"], positions["L"])
    second = bfs(maps, positions["L"], positions["E"])

    return -1 if first == -1 or second == -1 else first + second

BFS는 먼저 큐에 들어간 위치부터 꺼내므로, 처음 목표에 도착한 거리가 최단거리다. deque의 popleft()는 큐의 앞을 빠르게 꺼낸다.

한 번의 BFS로 상태를 나누는 방법

레버 전과 후에 같은 칸을 각각 방문할 수 있어야 한다면 visited[y][x][0], visited[y][x][1]처럼 세 번째 차원에 레버 상태를 둔다. 위치가 같아도 상태가 다르면 서로 다른 탐색 경로다.

양과 늑대

프로그래머스 공식 문제 페이지

현재 위치 하나만으로는 다음 선택을 결정할 수 없다. 이미 열어 둔 모든 자식 노드가 다음 후보가 되므로, 후보 노드 집합까지 탐색 상태에 저장한다.

from collections import deque

def solution(info, edges):
    tree = [[] for _ in info]
    for parent, child in edges:
        tree[parent].append(child)

    answer = 0
    queue = deque([(0, 1, 0, frozenset())])

    while queue:
        current, sheep, wolves, candidates = queue.popleft()
        answer = max(answer, sheep)

        next_candidates = set(candidates)
        next_candidates.update(tree[current])

        for next_node in next_candidates:
            remaining = next_candidates - {next_node}

            if info[next_node] == 0:
                queue.append((next_node, sheep + 1, wolves, frozenset(remaining)))
            elif sheep > wolves + 1:
                queue.append((next_node, sheep, wolves + 1, frozenset(remaining)))

    return answer

update()는 현재 노드의 자식을 후보에 더한다. next_candidates - {next_node}는 이번에 선택한 노드만 뺀 새 집합을 만든다. 분기마다 집합을 공유하면 다른 경로가 서로 영향을 주므로, 각 경로는 독립된 후보 집합을 가져야 한다.

길 찾기 게임

프로그래머스 공식 문제 페이지

y좌표가 높은 노드가 부모가 되고, 같은 높이에서는 x좌표가 작은 노드가 먼저다. y 내림차순, x 오름차순으로 정렬한 뒤 x좌표 기준 이진 트리를 만든다.

import sys

sys.setrecursionlimit(10**6)

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

def insert(parent, child):
    if child.x < parent.x:
        if parent.left is None:
            parent.left = child
        else:
            insert(parent.left, child)
    else:
        if parent.right is None:
            parent.right = child
        else:
            insert(parent.right, child)

def preorder(node, result):
    if node:
        result.append(node.node_id)
        preorder(node.left, result)
        preorder(node.right, result)

def postorder(node, result):
    if node:
        postorder(node.left, result)
        postorder(node.right, result)
        result.append(node.node_id)

def solution(nodeinfo):
    nodes = [
        Node(node_id, x, y)
        for node_id, (x, y) in enumerate(nodeinfo, start=1)
    ]
    nodes.sort(key=lambda node: (-node.y, node.x))

    root = nodes[0]
    for node in nodes[1:]:
        insert(root, node)

    pre_result = []
    post_result = []
    preorder(root, pre_result)
    postorder(root, post_result)

    return [pre_result, post_result]

(-node.y, node.x)는 y 큰 순서, x 작은 순서로 정렬한다. 전위 순회는 나 → 왼쪽 → 오른쪽, 후위 순회는 왼쪽 → 오른쪽 → 나 순서다. 한쪽으로 긴 트리가 만들어질 수 있어 재귀 한도를 충분히 늘려 둔다.

트리 문제 체크리스트

• 부모를 빠르게 찾아야 하면 child -> parent 딕셔너리를 만든다.
• 최단거리는 BFS와 큐를 먼저 검토한다.
• 같은 위치라도 레버 여부, 가진 후보 집합처럼 상태가 다르면 별도로 방문 처리한다.
• 정렬 기준이 여러 개면 key=lambda x: (첫째, 둘째)로 명확히 쓴다.
• 재귀 트리는 입력 깊이와 재귀 제한을 확인한다.

마무리

트리 문제는 노드만 보는 것이 아니라 부모 관계, 자식 목록, 현재 탐색 상태를 함께 설계하는 문제다. 다음 문제에서도 어떤 정보를 상태로 남길지부터 정리해 보자.

'Algorithm > Tree' 카테고리의 다른 글

코딩 테스트 합격자 되기 | 08 해시  (0)	2026.08.15