난생 처음 풀어본 골드2 (뚝배기 깨짐)

#2250번 트리의 높이와 너비 https://www.acmicpc.net/problem/2250

2250번: 트리의 높이와 너비

 

 

생각보다 어려운 문제가 아니라서 놀랬다.

난이도가 높아질수록 코드의 길이가 길어지는 듯 하다

그냥 조금씩 차분히 해나가면 된다.

 

아직은

내 머릿속에 있는 논리를

코드로 구현하는 능력이 많이 부족한 듯 하다.

 

더 많은 경험이 필요함을 느꼈다.

 

import sys
# 재귀 제한 설정
sys.setrecursionlimit(100000)
input = sys.stdin.readline

# 입력받기
N = int(input())
graph = [[] for _ in range(N+1)]
parent = [0]*(N+1)  # 루트 노드 찾기.
for _ in range(N):
    n, l, r = list(map(int, input().split()))
    graph[n].append(l)
    graph[n].append(r)

    # 하위 노드의 parent 배열에 1씩 더해준다. -> 0인 index가 root 노드
    if l != -1:
        parent[l] += 1
    if r != -1:
        parent[r] += 1


# row 별로 해당되는 value를 넣어준다.
matrix = [[] for _ in range(N+1)]
# column을 세준다.
column_num = 1

# 중위순회를 해야한다. 왼쪽 -> 루트 -> 오른쪽


def dfs_inorder(node, level):
    global column_num
    l, r = graph[node]
    if l > 0:
        # 하위 노드로 갈수록 row가 한단계 더 깊어진다.
        dfs_inorder(l, level+1)
    matrix[level].append(column_num)
    column_num += 1
    if r > 0:
        # 하위 노드로 갈수록 row가 한단계 더 깊어진다.
        dfs_inorder(r, level+1)


# get root node
root = 0
for i in range(1, N+1):
    if parent[i] == 0:
        root = i
        break

dfs_inorder(root, 1)

# 답 구하기. [ level, width ]
answer = [1, max(matrix[1]) - min(matrix[1]) + 1]
for r in range(2, N+1):
    if matrix[r]:
        tmp = max(matrix[r]) - min(matrix[r]) + 1
        if answer[1] < tmp:
            answer = [r, tmp]

print(" ".join(map(str, answer)))

아이디어는

1. 이진 트리를 중위순회 (왼쪽 노드, 루트 노드, 오른쪽 노드) 할것.

2. 주어진 그래프 데이터에서 루트노드를 찾을것

3. 중위순회를 하면서 깊이와 너비를 찾을것

  -> [너비 => 연산 횟수, 깊이 => 재귀 횟수]

 

3번 아이디어가 떠오르지 않았다.

뭔가 굉장히 복잡하게 생각했던 것 같다.

알고보면 별거 아닌데...

 

 

여기에 추가 설명을 하자면

이진 트리 (자식 노드가 2개 이하인 트리)에서는

 

전위 순회

  (루트 -> 왼쪽자식 -> 오른쪽자식)

중위순회

  (왼쪽자식 -> 루트 -> 오른쪽 자식)

후위순회

  (왼쪽자식 -> 오른쪽자식 -> 루트)

 

라는 개념이 존재한다.

 

다음 문제를 풀어보면 도움이 된다.

 

#1991번 트리순회 https://www.acmicpc.net/problem/1991

1991번: 트리 순회

N = int(input())
graph = {}

for _ in range(N):
    s, l, r = input().split()
    graph[s] = []

    for i in [l, r]:
        if i == ".":
            graph[s].append("")
        else:
            graph[s].append(i)

# 전위순회
order = []


def preOrder(node):
    order.append(node)
    for leef in graph[node]:
        if len(leef) > 0:
            preOrder(leef)


preOrder("A")
print("".join(order))

# 중위순회
order = []


def inOrder(node):
    l, r = graph[node]
    if len(l) > 0:
        inOrder(l)
    order.append(node)
    if len(r) > 0:
        inOrder(r)


inOrder("A")
print("".join(order))

# 후위순회
order = []


def postOrder(node):
    l, r = graph[node]
    if len(l) > 0:
        postOrder(l)
    if len(r) > 0:
        postOrder(r)
    order.append(node)


postOrder("A")
print("".join(order))