[Python] 백준 2250번: 트리의 높이와 너비

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

2250번: 트리의 높이와 너비

 

input = sys.stdin.readline

n = int(input())
tree = [[] for _ in range(n+1)]
childNode = [[0, 0] for _ in range(n+1)]
node = [[] for _ in range(n+1)]
ans = [-1, -1]
root = [i for i in range(1, n+1)]
for _ in range(n):
    a, b, c = map(int, input().split())
    tree[a] = (max(0, b), max(0, c))
    if b != -1:
        root.remove(b)
    if c != -1:
        root.remove(c)

def childSearch(x):
    if not tree[x][0] and not tree[x][1]:
        return 1
    if tree[x][0]:
        childNode[x][0] += childSearch(tree[x][0])
    if tree[x][1]:
        childNode[x][1] += childSearch(tree[x][1])
    return sum(childNode[x]) + 1

def dfs(x, now, s, e):
    if s == e:
        node[x].append(s)
        return
    node[x].append(e-childNode[now][1])
    if childNode[now][0]:  # 왼쪽
        dfs(x+1, tree[now][0], s, e-1-childNode[now][1])
    if childNode[now][1]:  # 오른쪽
        dfs(x+1, tree[now][1], s+1+childNode[now][0], e)

childSearch(root[0])
dfs(1, root[0], 1, n)
for x in range(1, n+1):
    if node[x]:
        area = max(node[x]) - min(node[x])
        if area > ans[1]:
            ans = [x, area]

print(ans[0], ans[1]+1)

중위순회라는 생각을 하지못하고 무지성으로 풀었다.

1. 왼쪽자식과 오른쪽 자식 노드의 갯수를 구해준다.

2. 범위값을 바꾸어 주면서 현재 깊이에 들어갈 수를 넣어준다.

 

다른 사람들의 코드를 보니... 진짜 무지성으로 푼거같다..