2250번: 트리의 높이와 너비 (트리, 재귀) - Fastcampus

www.acmicpc.net/problem/2250

2250번: 트리의 높이와 너비

# 각 레벨의 너비 중 최대값
def in_order(parent, row=1):
    lc, rc = graph[parent]

    if lc != -1:
        in_order(lc, row + 1)

    global col, maxRow
    col += 1
    minCol[row] = min(minCol[row], col)
    maxCol[row] = max(maxCol[row], col)
    maxRow = max(maxRow, row)

    if rc != -1:
        in_order(rc, row + 1)


N = int(input())
graph = [(0, 0) for _ in range(N+1)]
parent = [0] * (N+1)
for _ in range(N):
    p, lc, rc = map(int, input().split())
    graph[p] = (lc, rc)
    if lc != -1:
        parent[lc] = p
    if rc != -1:
        parent[rc] = p

# 전역변수
col = 0
minCol = [N] * (N+1)  # [19, 10,  3,  2,  1,  4,  6]
maxCol = [1] * (N+1)  # [ 1, 10, 15, 19, 18, 16, 17]
maxRow = 1

# 유의사항: 루트 노드를 구해야 한다
root = 0
for i in range(1, N+1):
    if parent[i] == 0:
        root = i
in_order(root)

max_w, lv = 1, 1
for i in range(1, maxRow+1):
    w = maxCol[i] - minCol[i] + 1
    if w > max_w:
        max_w = w
        lv = i
print(lv, max_w)

 

다른 풀이: 연결정보를 (노드 클래스)로 표현

 

class Node:
    def __init__(self, p, lc, rc):
        self.data = p
        self.lc = lc
        self.rc = rc
        self.parent = -1  # 부모노드 (루트노드를 찾기 위해 추가)


def in_order(parent, row=1):
    node = graph[parent]

    if node.lc != -1:
        in_order(node.lc, row + 1)

    global col, maxRow
    col += 1
    minCol[row] = min(minCol[row], col)
    maxCol[row] = max(maxCol[row], col)
    maxRow = max(maxRow, row)

    if node.rc != -1:
        in_order(node.rc, row + 1)


N = int(input())
graph = [Node(i, 0, 0) for i in range(N+1)]
for _ in range(N):
    p, lc, rc = map(int, input().split())
    graph[p].lc = lc
    graph[p].rc = rc
    if lc != -1:
        graph[lc].parent = p
    if rc != -1:
        graph[rc].parent = p

col = 0
maxCol = [1] * (N+1)
minCol = [N] * (N+1)
maxRow = 1

root = 0
for i in range(1, N+1):
    if graph[i].parent == -1:
        root = i
in_order(root)

max_w, lv = 1, 1
for i in range(1, maxRow+1):
    w = maxCol[i] - minCol[i] + 1
    if w > max_w:
        max_w = w
        lv = i
print(lv, max_w)