BOJ_2250 트리의 높이와 너비

TOC {:toc}

이 글은 백준 온라인 저지의 2250번 문제를 풀이한 것을 모아놓은 글입니다.

일종의 연습 기록이며 제가 정답을 받은 코드와 참고할만한 다른 코드를 같이 기록합니다. 필요한 경우 코드에 대한 해설을 기록합니다만 코드는 통과했어도 해설은 틀릴 수 있기 때문에 가볍게 참고해주시길 부탁드립니다. 피드백은 편하신 방법으로 자유롭게 주시면 감사하겠습니다.

2021.05.20 (Python)

메모리	시간	코드 길이
31244 KB	104 ms	920 B

단계	시작 시각	끝난 시각
문제 이해	21:31:38	21:33:28
풀이 생각	21:33:57	21:39:25
코딩	22:40:27	23:26:18
디버깅 1	23:34:31	23:40:29
디버깅 2	11:02:43	13:16:22

import sys
input: lambda: sys.stdin.readline().rstrip()

# tree 관계를 나타내는 인덱스
# Class를 정의하는 대신 리스트를 사용한다.
PARENT = 0
LEFT = 1
RIGHT = 2

# 중위 순회
def inorder(node, level):
    global col

    if node < 0:
        return

    level += 1
    inorder(tree[node][LEFT], level)
    col += 1
    if level in width:
        width[level][-1] = col
    else:
        width[level] = [col, col]
    inorder(tree[node][RIGHT], level)

N = int(input())

tree = {}
width = {}
col = 0
root = -1

# tree 초기화
for i in range(1, N + 1):
    tree[i] = [-1, -1, -1]

# 입력에 따라 트리 구성
for _ in range(N):
    num, left, right = map(int, input().split())
    tree[num][LEFT] = left
    tree[num][RIGHT] = right
    if left in tree:
        tree[left][PARENT] = num
    if right in tree:
        tree[right][PARENT] = num

# root 결정
for x in tree:
    if tree[x][PARENT] == -1:
        root = x

inorder(root, 0)

# 입력받은 col의 최소, 최댓값으로 width 계산
for row in width:
    width[row] = width[row][-1] - width[row][0] + 1

print(*max(width.items(), key=lambda x: (x[1], -x[0])))

아이디어 & 풀이

중위 순회하면 열 순서대로 순회할 수 있다.

열을 탐색할 때마다 해당 레벨(행)의 마지막(최대) 열을 업데이트한다.

레벨(행)은 재귀 함수를 실행할 때마다 한 개씩 높여서 인자로 넘겨준다.

디버그

처음에는 col이 순차 증가하지 않아서 틀린 줄 알았다.
- 매번 현재 col과 min, max를 비교해서 넣어주거나 모든 열을 입력받고 이후에 width를 계산할 때 min, max를 계산하는 방식으로 바꾸면 됐었는데
- 실제로 col은 순차 증가했었고 틀린 원인이 아니었다.
루트 노드 지정을 따로 해주지 않고 1로 입력해서 틀렸었다.
- 노드가 1부터 N까지라고 했지 루트가 1이라는 조건은 없었는데 루트가 고정이었던 이전 문제 때문에 헷갈린 것 같다.
- 루트 노드를 찾는 코드를 추가해서 해결했다.

피드백

inorder 안에서 level에 1을 더해주는 것을 따로 하지 말고, 재귀 함수의 인자로 level + 1을 넘겨줘도 된다.

2022.04.07 (JS)

메모리	시간	코드 길이
16924 KB	248 ms	1077 B

단계	시작 시각	끝난 시각
문제 이해	16:28:23	16:30:42
풀이 생각	16:44:03	16:46:07
코딩	16:46:16	17:34:03
디버깅	20:37:56	20:47:43

const fs = require("fs");
const input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");

function main() {
    function inorder(n, level) {
        if (n === -1) return;

        const [childL, childR] = node[n];

        inorder(childL, level + 1);
        count += 1;
        coord[level].push(count);
        inorder(childR, level + 1);
    }

    let count = 0;
    inorder(root, 1);

    const width = Array(N + 1).fill(0);
    coord.forEach((arr, i) => {
        if (arr.length) width[i] = arr[arr.length - 1] - arr[0] + 1;
    });

    const max = Math.max(...width);
    console.log(width.indexOf(max), max);
}

const [tempN, ...lines] = input;
const N = parseInt(tempN);
const node = Array(N + 1);

const isChild = Array(N + 1).fill(false);
isChild[0] = true;

lines.forEach((line) => {
    const [p, l, r] = line.split(" ").map((n) => parseInt(n));
    node[p] = [l, r];
    if (l !== -1) isChild[l] = true;
    if (r !== -1) isChild[r] = true;
});
const coord = Array(N + 1)
    .fill()
    .map((i) => []);
const root = isChild.indexOf(false);

main();

디버그

루트노드가 항상 1이 아니라서 루트노드를 따로 구해줘야 했다.

참고 답안 1

# 리스트 사용
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 8)

def inorder(node, level):
    global col

    if tree[node][0]:
        inorder(tree[node][0], level + 1)
    col += 1
    c_min[level] = min(c_min[level], col)
    c_max[level] = max(c_max[level], col)
    if tree[node][1]:
        inorder(tree[node][1], level + 1)

n = int(input())
tree = [[0, 0] for i in range(n + 1)]
p = [False] * (n + 1)

for _ in range(n):
    num, l, r = map(int, input().split())
    if l != -1:
        tree[num][0] = l
        p[l] = True
    if r != -1:
        tree[num][1] = r
        p[r] = True

root = p.index(False, 1)

c_min = [n] * (n + 1)
c_max = [0] * (n + 1)
col = 0

inorder(root, 0)

i = 0
max_l = 1
max_w = 1
while c_min[i] != n and c_max[i] != 0:
    w = c_max[i] - c_min[i] + 1
    if max_w < w:
        max_l = i
        max_w = w
    i += 1

print(max_l, max_w)

참고 답안 2

# 클래스 사용
class Node:
    def __init__(self, num, left, right):
        self.parent = -1
        self.num = num
        self.left = left
        self.right = right

def inorder(node, level):
    global depth, col
    
    depth = max(depth, level)
    if node.left != -1:
        inorder(tree[node.left], level + 1)
    
    c_min[level] = min(c_min[level], x)
    c_max[level] = max(c_max[level], x)
    col += 1
    
    if node.right != -1:
        inorder(tree[node.right], level + 1)

N = int(input())

# 트리
tree = {}
# 각 level(인덱스)의 최소 열을 담아두는 리스트
c_min = [N]
# 각 level(인덱스)의 최대 열을 담아두는 리스트
c_max = [0]
root = -1
depth = 1
col = 1

# tree, c_min, c_max 초기화
for i in range(1, N + 1):
    tree[i] = Node(i, -1, -1)
    c_min.append(N)
    c_max.append(0)

# tree 생성
for _ in range(N):
    number, left, right = map(int, input())
    tree[number].left = left
    tree[number].right = right
    if left != -1:
        tree[left].parent = number
    if right != -1:
        tree[right].parent = number

# root 지정
for i in range(1, N + 1):
    if tree[i].parent == -1:
        root = i
        break

inorder(tree[root], 1)

max_level = 1
max_width = 1

for i in range(2, depth + 1):
    width = c_max[i] - c_min[i] + 1
    if max_width < width:
        max_level = i
        max_width = width

print(max_level, max_width)