https://www.acmicpc.net/problem/2250
공부 날짜 : 2023.02.09
정답 참조 여부 : X
2진 트리를 그릴 때 하나의 열에는 하나의 노드만 존재하고 빈 열이 없어야한다. 또한, 우측노드는 부모노드보다 우측에 좌측 노드는 부모노드보다 좌측에 그리도록 했을 때
각 행에서 너비가 가장 넓은 레벨을 찾는 문제이다.
새로운 경험을 해본 문제였다.
항상 DFS는 재귀함수로 문제를 풀었는데, 이 문제를 재귀함수로 풀면 RecursionError이 나왔다.
물론 sys.setrecursionlimit(100000)로 재귀깊이를 무려 10만으로 해줬는데도 RecursionError가 나왔다.
그래서 DFS를 스택으로 풀어야 했는데, 스택으로 구현해본건 난생 처음이였다.
단순히 스택으로 DFS를 구현 할 수는 있겠는데, 이 문제에서는 다음 노드를 탐색한 다음에 다시 자신에게 돌아 왔어야 했다.
1 > 2 > 4 > 8 > 4 > 2 > 5
8까지 DFS로 탐색을 마치면 보통 5로 넘어가는데 이 문제에서는 4로 돌아와 3레벨, 2행이 4라는걸 기록해 줘야했다.
그래서 조금 헷갈리고 구현하는데 애먹었다.
겪은 문제중에 또 다른 문제는 root_node를 찾지 못한것이다.
노드를 입력받아 부모노드와 자식노드를 기록 해준 뒤
for i in range(1, n+1):
if tree[i][0] == -1:
root_node = i
break로 root_node를 찾아줬는데, 55%에서 NameError가 발생했다.
바로 위에 root_node = 0을 해줬더니 55%에서 틀렸다고 나온걸 보면 분명 root_node를 못찾는 것이였다.
문제는 파이썬 언어의 특징이였는데
tree = [[-1, [0, 0]] for _ in range(n+1)]
# 트리 입력받기
for i in range(n):
n1, a, b = map(int, input().split())
tree[n1][1] = [a, b]
tree[a][0] = n
tree[b][0] = n로 입력을 받는데, 이 경우 leap_node라서 -1이 들어오면 원하는 방향으로 코드가 작동하지 않는다.
edge case :
2
2 1,-1
1, -1, -1
이 입력되면 2번 노드의 부모노드가 2번이 되어 버린다.
그래서 단순하게
# 트리 입력받기
for i in range(n):
n1, a, b = map(int, input().split())
tree[n1][1] = [a, b]
if a != -1:
tree[a][0] = n
if b != -1:
tree[b][0] = n로 바꿔 줬더니 정답으로 나왔다.
DFS를 스택으로 구현하는게 많이 색달랐다.
이제까지 항상 DFS는 재귀로 구현했고, RecursionError이 발생하면 항상sys.setrecursionlimit()로 재귀깊이를 바꿔줬다. 하지만 기업 코테에서 import sys를 못하게 하는 경우가 있어서 어쩌나 싶은 작은 고민이 있었는데 스택으로 구현도 가능해 졌다.
소스코드
import sys
from copy import deepcopy
input = sys.stdin.readline
###############################################################
# dfs용 함수
def dfs(start_node):
global position, tree_picture
visit = [start_node]
visited = [0 for _ in range(n+1)]
level = 0
while visit:
node = visit.pop()
# 자식 노드가 없으면 다시 돌아감
if node == -1:
level -= 1
continue
# 다음 레벨 도달시 새로운 레벨 추가
else:
if len(tree_picture) <= level:
tree_picture.append(deepcopy(level_data))
# 이미 방문한 노드면?
# 오른쪽 노드 탐색이 완료된 상태
# 자신을 기록하고 다음 왼쪽노드 탐색 시작
if visited[node] == 1:
tree_picture[level][0][position] = node
# 기록시 해당 레벨의 최 좌측, 최 우측 위치 갱신
if tree_picture[level][1] > position:
tree_picture[level][1] = position
if tree_picture[level][2] < position:
tree_picture[level][2] = position
# 위치 + 1
position += 1
# 오른쪽 탐색완료 표시
visited[node] += 1
level += 1
continue
# 왼쪽 탐생이 끝난 상태이면
elif visited[node] == 2:
# 레벨 낮춰서 돌아감
level -= 1
continue
# 방문 노드 아니면 방문처리
visited[node] += 1
# 이 장소에 새로 오는거면 다음 경로들 추가
# 왼쪽 노드 추가
visit.append(node)
visit.append(tree[node][1][1])
# 오른쪽 노드가 탐색 완료되었는지 판단하기 위한 자신 추가
visit.append(node)
# 오른쪽 먼저 탐색하기 위해서 오른쪽을 나중에
visit.append(tree[node][1][0])
level += 1
###############################################################
n = int(input())
tree = [[-1, [0, 0]] for _ in range(n+1)]
# 트리 입력받기
for i in range(n):
n1, a, b = map(int, input().split())
tree[n1][1] = [a, b]
if a != -1:
tree[a][0] = n
if b != -1:
tree[b][0] = n
# 루트노드 찾기
root_node = 0
for i in range(1, n+1):
if tree[i][0] == -1:
root_node = i
break
# print("root_node : ", root_node)
position = 0
# 각 레벨의 데이터 레벨의 모습과, 최 좌측, 최 우측이 저장됨
level_data = [[0 for _ in range(n)], n, -1]
# 0 레벨 상태 추가하기
tree_picture = [deepcopy(level_data)]
# 깊이 0, 1번 노드부터 dfs시작
dfs(root_node)
# for i in tree_picture:
# print(i)
# 각 레벨의 최대 너비 탐색 및 갱신
max_length = 0
max_level = 0
for i in range(len(tree_picture)):
if max_length < tree_picture[i][2] - tree_picture[i][1] + 1:
max_length = tree_picture[i][2] - tree_picture[i][1] + 1
max_level = i+1
print(max_level, max_length)
