백준 2250 문제 링크: https://www.acmicpc.net/problem/2250
📑 문제 설명
1. 이진트리가 주어지고 이진 트리를 다음과 같은 규칙에 따라 격자 모양 틀 속에 그리고자 함
2. 규칙은 다음과 같음
1. 이진트리에서 같은 레벨(depth)을 갖는 노드는 같은 행에 위치
2. 한 열에는 한 노드만 존재
3. 임의의 노드 왼쪽 부트리에 있는 노드들은 해당 노드보다 왼쪽의 열에 위치하고, 오른쪽 부트리에 있는 노드들은 해당 노드보다 오른쪽 열에 위치
4. 노드가 배치된 가장 왼쪽 열과 오른쪽 열 사이엔 아무 노드도 없이 비어있는 열은 없음
3. 2번에 명시된 규칙을 따를 때 같은 레벨 안에서 가장 큰 너비(가장 오른쪽에 있는 열번호 - 가장 왼쪽에 있는 열번호 + 1)를 찾아야 한다.
입력: 첫째 줄에 노드 개수를 나타내는 N이 주어지고 다음 N개 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 오른쪽 자식 노드 번호가 순서대로 주어진다. 노드들의 번호는 1~N까지이며, 자식이 없는 경우에는 자식 노드 번호에 -1이 주어진다.
출력: 첫째 줄에 너비가 가장 넓은 레벨과 그 레벨의 너비를 순서대로 출력한다.
단, 가장 큰 너비를 갖는 레벨이 2개 있을 때는 더 작은 레벨을 출력한다.
💡 문제 해결 방법
알고리즘: 중위 순회, bfs
알고리즘 선택 이유
1. 가장 왼쪽에 있는 노드와 가장 오른쪽에 있는 노드를 파악해야 하므로, 왼쪽 --> 루트 --> 오른쪽 순서로 탐색하는 중위선회가 적절하다.
예외처리 및 추가 내용
1. 1번 노드가 반드시 루트 노드가 아니므로 이진 트리를 입력받을 때 루트노드로써 1회, 자식노드로써는 0회 입력된 노드를 찾는다.
2. 찾은 루트노드로부터 왼쪽으로 내려가 가장 왼쪽에 있는 노드를 찾는다.
3. 가장 왼쪽에 있는 노드를 1열에 위치했다고 가정하고 루트노드, 오른쪽 노드를 탐색할 때마다 열 번호 + 1을 해준다.
- 같은 레벨임을 체크해야 함
스터디 내용
1. 트리를 구성하기
2. 레벨과 열번호를 알아야 함
- 레벨은 부모 depth + 1로 하면 됨
- 중위 탐색: 각 노드의 열번호 나옴
- 각 레벨에서 min(left)과 max(right)를 구하여 차이 계산
3. 중위 탐색
4. 모든 노드에 대해 레벨과 열번호를 구하라는 문제
💻 코드
import sys
from collections import deque
n = int(sys.stdin.readline())
tree = [[-1, -1, -1] for x in range(n+1)]
for i in range(n):
node, lc, rc = map(int, sys.stdin.readline().split())
tree[node][1] = lc
tree[node][2] = rc
tree[lc][0] = n
tree[rc][0] = n
root = -1
for i in range(1, n+1):
if tree[i][0] == -1:
root = i
visit = [[-1, -1] for x in range(n+1)] # r: level, c: dist
def bfs(root):
maxdepth = 0
queue = deque([root])
visit[root][0] = 0
while queue:
node = queue.popleft()
lc = tree[node][1]
rc = tree[node][2]
if lc != -1:
if visit[lc][0] == -1:
visit[lc][0] = visit[node][0] + 1
maxdepth = max(visit[lc][0], maxdepth)
queue.append(lc)
if rc!= -1:
if visit[rc][0] == -1:
visit[rc][0] = visit[node][0] + 1
maxdepth = max(visit[rc][0], maxdepth)
queue.append(rc)
return maxdepth
global dist
dist = 0
def inorder_search(node):
global dist
if tree[node][1] != -1:
inorder_search(tree[node][1])
dist += 1
visit[node][1] = dist
if tree[node][2] != -1:
inorder_search(tree[node][2])
maxdepth = bfs(root)
inorder_search(root)
maxdist = 0
minlevel = 1e10
if n == 1:
print(1)
print(1)
else:
for d in range(maxdepth+1):
minval = 1e10
maxval = 0
for i in range(1, n + 1):
if d == visit[i][0]:
minval = min(visit[i][1], minval)
maxval = max(visit[i][1], maxval)
if maxdist < maxval-minval+1:
minlevel = d+1
maxdist = maxval-minval+1
print(minlevel)
print(maxdist)
💟 추가적으로 알게 된 점
- 중위 탐색: 왼 -> 부모 -> 오
- 왼쪽 자식이 없을 때까지 들어감- 왼쪽 자식 방문 후 리턴하면 현재 노드는 부모로 자연스럽게 부모 노드 방문
- 방문 후 오른쪽 자식 방문 --> 근데 여기서도 왼쪽 자식 노드가 있는지 먼저 확인하여 왼쪽 자식이 없을 때까지 들어간 다음 부모, 오른쪽 노드를 거침
