트리의 높이와 너비 (2250번) - 백준 (BOJ)

https://www.acmicpc.net/problem/2250

2250번: 트리의 높이와 너비

 

 

백준 - 트리의 높이와 너비 (2250번)

 

난이도 : Gold 2

알고리즘&자료구조 : DFS (깊이우선탐색)

---

★ 핵심 Idea ★

 

◎ 루트 노드를 기준으로, 트리의 각 깊이 별 노드의 최소 최대 위치를 DFS로 구한다.

 

 

< 전체 코드 >

 

import sys
input = sys.stdin.readline


class Tree():
    def __init__(self, N):
        self.tree = [(0, 0) for _ in range(N+1)]
        is_root = [True] * (N+2)
        for _ in range(1, N+1):
            p, l, r = map(int, input().split())
            self.tree[p] = (l, r)
            is_root[l] = is_root[r] = False
        for i in range(1, N+1):
            if is_root[i]:
                root = i
                break
        self.children = [[0, 0] for _ in range(N+1)]
        self.edges = [[10000, -10000] for _ in range(N+1)]
        self._dfs_count(root)
        self._dfs_breadth(root, 1, 0)
        
        widest = [1, 1]
        for i in range(2, N+1):
            cur = self.edges[i][1] - self.edges[i][0] + 1
            if cur < 0:
                break
            if widest[1] < cur:
                widest = [i, cur]
        self.answer = widest

    
    def _dfs_count(self, node):
        cnt = 1
        for i in range(2):
            cur = 0 if self.tree[node][i] == -1 else self._dfs_count(self.tree[node][i])
            self.children[node][i] = cur
            cnt += cur
        return cnt
    

    def _dfs_breadth(self, node, depth, loc):
        if loc < self.edges[depth][0]:
            self.edges[depth][0] = loc
        if loc > self.edges[depth][1]:
            self.edges[depth][1] = loc
        
        for i in range(2):
            cnode = self.tree[node][i]
            if cnode == -1:
                continue
            cloc = loc + (1 if i else -1) * (self.children[cnode][i^1] + 1)
            self._dfs_breadth(cnode, depth+1, cloc)


if __name__ == '__main__':
    tree = Tree(int(input()))
    print(*tree.answer)

 

 

---

 

① "self.tree"에 각 노드의 왼쪽과 오른쪽 자식 노드를 기록하고, root 노드를 찾는다.

 

self.tree = [(0, 0) for _ in range(N+1)]
is_root = [True] * (N+2)
for _ in range(1, N+1):
    p, l, r = map(int, input().split())
    self.tree[p] = (l, r)
    is_root[l] = is_root[r] = False
for i in range(1, N+1):
    if is_root[i]:
        root = i
        break

 

 

 

② "_dfs_count" 함수를 통해, 각 노드의 오른쪽과 왼쪽 자식 노드들의 개수를 "self.children"에 저장한다.

 

def _dfs_count(self, node):
    cnt = 1
    for i in range(2):
        cur = 0 if self.tree[node][i] == -1 else self._dfs_count(self.tree[node][i])
        self.children[node][i] = cur
        cnt += cur
    return cnt


self.children = [[0, 0] for _ in range(N+1)]
self._dfs_count(root)

 

 

 

③ 루트노드의 위치를 0으로 두고,

0을 기준으로 각 노드가 존재하는 깊이에서의 위치가, 해당 깊이에서의 최솟값 혹은 최댓값이라면 "self.edges"에 저장한다.

 

def _dfs_breadth(self, node, depth, loc):
    if loc < self.edges[depth][0]:
        self.edges[depth][0] = loc
    if loc > self.edges[depth][1]:
        self.edges[depth][1] = loc
    
    for i in range(2):
        cnode = self.tree[node][i]
        if cnode == -1:
            continue
        cloc = loc + (1 if i else -1) * (self.children[cnode][i^1] + 1)
        self._dfs_breadth(cnode, depth+1, cloc)
        
self.edges = [[10000, -10000] for _ in range(N+1)]
self._dfs_breadth(root, 1, 0)

 

 

 

④ 가장 범위가 넓은 깊이와 범위의 크기를 찾고,

그 값들을 출력한다.

 

widest = [1, 1]
for i in range(2, N+1):
    cur = self.edges[i][1] - self.edges[i][0] + 1
    if cur < 0:
        break
    if widest[1] < cur:
        widest = [i, cur]
self.answer = widest

print(*tree.answer)