백준 2250 트리의 높이와 너비

문제

👀 문제 사이트 : https://www.acmicpc.net/problem/2250

풀이

난이도 : Gold II

• 이 문제는 dfs를 이용하여 각 노드에 행과 열값을 구해 풀이하였다.

1. 노드를 입력받으면서 child와 parent에 대한 정보를 저장한다.
   (입력받을 때, 노드 번호도 주어지므로 노드 번호에 따라 인덱스를 부여해 데이터를 저장한다.)
2. 모든 노드 중에 parent가 없는 노드가 하나 있는데, 그 노드를 찾아 root 노드로 정한다.
3. dfs로 노드를 탐색해나가면서 depth와 column 값을 구해주며 기록한다.
   -> column 값이 child에 따라 달라지므로, 이 점만 유의하면 된다.
4. depth(level 혹은 행)별로 문제에서 구해야 하는 값을 찾아가며 답을 찾는다.

코드

    n = int(input())

    # col, level, index
    col_level = [[0, 0, i] for i in range(n+1)]

    child = [[] for _ in range(n+1)]
    parent = [[] for _ in range(n+1)]

    for _ in range(n):
        a, b, c = map(int, input().split())
        if b != -1:
            parent[b].append(a)
        if c != -1:
            parent[c].append(a)
        child[a].append(b)
        child[a].append(c)

    # root node index
    p_index = -1
    for i in range(1, len(parent)):
        if parent[i] == []:
            p_index = i
            break

    # current는 현재 column
    current = 1
    # i는 현재 index, l은 현재 level
    def dfs(i, l):
        global current
        left, right = child[i]
        col_level[i][1] = l

        if left != -1:
            dfs(left, l+1)
        col_level[i][0] = current
        current = current + 1
        if right != -1:
            dfs(right, l+1)

    dfs(p_index, 1)
    col_level.sort(key=lambda x: (x[1], x[0]))


    # search max value
    first = 0
    lev = 0
    max_result = 0
    result_level = 0

    for i in range(1, len(col_level)):
        if lev != col_level[i][1]:
            lev = col_level[i][1]
            first = col_level[i][0]

        if i+1 >= len(col_level) or (i+1 < len(col_level) and col_level[i+1][1] != lev):
            x = col_level[i][0] - first + 1
            if max_result < x:
                max_result = x
                result_level = lev

    print(result_level, max_result)