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

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

2250번: 트리의 높이와 너비

 

구현이 까다로웠던 그래프 탐색 문제이다.

 

문제를 요약하자면 트리의 노드들을 2차원 좌표공간에 매칭시키는 문제다. 루트 노드부터 시작해서 자식으로 내려갈때(레벨이 증가할 때) 마다 x좌표(행)가 증가하,고 부모의 왼쪽 자식은 부모보다 y좌표(열)가 작으며 오른쪽 자식은 더 크다. 하나의 열에는 오직 한 개의 노드만 들어갈 수 있고 트리의 가장 왼쪽에있는 노드와 가장 오른쪽에있는 노드 사이에 비어있는 열이 있으면 안된다. 이때 각 행마다 왼쪽 끝과 오른쪽 끝에있는 노드 사이의 거리를 구하여, 그 값이 가장 최대인 행과 값을 출력하는 문제다.

 

루트 노드의 2차원 좌표를 알면 나머지 노드들의 좌표도 알 수 있다. 하지만 그 전에 먼저, 각 노드마다 좌 우 서브트리에 존재하는 노드들의 개수를 알아내야 한다. 문제의 예시를 봐 보자. 루트 노드인 1번의 왼쪽과 오른쪽에는 각각 9개의 노드가 있다.  왼쪽에 있는 노드들이 각각 열에 배치되기 때문에 1번 노드의 좌표는 (1, 10)이다. 이번엔 1번의 왼쪽 자식인 2번 노드를 보자. 2번 노드의 오른쪽에는 6개의 노드가 존재한다. 따라서 1번 노드가 있는 열(y좌표)에서 (6+1)만큼 떨어진 곳에 존재한다. 그러므로 2번 노드의 좌표는 (2, 3)이다.

 

위와 같은 과정을 반복하면 모든 노드들의 2차원 좌표를 구할 수 있고, 그 좌표를 이용해서 구하고자 하는 값을 계산할 수 있다. 재귀문을 이용한 DFS를 통해 각 노드마다 왼쪽 및 오른쪽에 존재하는 노드의 개수를 구하고, BFS를 통해 루트 노드를 시작으로 행을(x 좌표) 증가시켜가며 그 행에 존재하는 노드들의 좌표를 계산한다. 마지막으로 모든 행을 검사하며 (행에 존재하는 노드 y좌표의 최댓값 - 최솟값 + 1) 를 계산해주어 각 행별로 비교해주면 된다.

 

문제 예시에는 1번이 루트 노드로 돼있지만, 문제 어디에도 1번이 루트 노드라는 말은 없다. 따라서 트리의 루트 노드를 구해주는 과정이 추가적으로 필요하다. 항상 느끼는거지만 문제를 꼼꼼히 읽는 습관을 들여야겠다.

 

import sys
input = sys.stdin.readline
from collections import deque

class Node:
    x, y = 0, 0
    lc, rc = 0, 0
    ln, rn = 0, 0
    p = 0

def dfs(i):
    lc, rc = 0, 0
    ln, rn = g[i].ln, g[i].rn
    if ln > 0:
        lc = dfs(ln)
    if rn > 0:
        rc = dfs(rn)

    g[i].lc = lc
    g[i].rc = rc

    return lc + rc + 1

def bfs(i):
    g[i].x, g[i].y = 1, 1 + g[i].lc
    q = deque([i])
    while q:
        k = q.popleft()
        l, r = g[k].ln, g[k].rn
        f[g[k].x].append(g[k].y)

        if l > 0:
            g[l].x = g[k].x + 1
            g[l].y = g[k].y - g[l].rc - 1
            q.append(l)
        if r > 0:
            g[r].x = g[k].x + 1
            g[r].y = g[k].y + g[r].lc + 1
            q.append(r)

def find_root(i):
    if g[i].p == 0:
        return i
    return find_root(g[i].p)

n = int(input())
g = dict([(i, Node()) for i in range(1, n + 1)])
f = [[] for _ in range(50)]
for i in range(n):
    x, y, z = map(int, input().split())
    if y > 0:
        g[x].ln = y
        g[y].p = x
    if z > 0:
        g[x].rn = z
        g[z].p = x

root = find_root(1)
dfs(root)
bfs(root)

mi, mv = 0, 0
for i in range(1, 50):

    if len(f[i]) == 0:
        break

    v = max(f[i]) - min(f[i]) + 1
    if mv < v:
        mv = v
        mi = i
print(mi, mv)