https://www.acmicpc.net/problem/2250
2250번: 트리의 높이와 너비첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다.www.acmicpc.net
와 진짜 나한테는 개어렵다.
다른사람의 풀이를 참고했다.
먼져, 정보를 받아서 tree를 구성한다.
root가주어지지 않기에, 각각의 트리에 parent를 -1로 초기화시켜놓고,
각각의 자식노드들의 parent를 업데이트한다.
이후 트리에서 parent가 -1인 노드가 root이다.
루트에서 중위순회를 시작한다. 이때 레벨정보를 넘겨줘야한다.
레벨정보는 root일때 1이고, 한단계 들어갈때마다 1씩 증가시킨다.
가장 먼저 실행하는 곳은, 가장 왼쪽에 있는 노드일것이다.
전역변수인 position을 0으로 선언하고, 노드를 방문할때마다 1씩 더해준다.
result에 레벨정보에 따라서, 각 레벨의 position을 한데 묶는다. (dict)
여기까지 끝났으면, 이제 답만 구하면 된다.
result의 레벨을 정렬하고, 낮은 레벨부터 최대-최소의 값을 구한다.
같을 경우에는 레벨이 낮은게 우선이므로, 클 때만 레벨과 최대-최소를 업데이트해준다.
이후 출력해준다.
내가 트리구조를 첨 접해서인지 너무 어렵다진짜. 아이디어를 얻지않는 이상 혼자서 못풀겠다.
import sysinput=sys.stdin.readlineclass Node:
def __init__(self,data,left,right,parent): self.data=data
self.left=left self.right=right self.parent=parent
position=0 #가장 왼쪽부터1씩증가시키면서번호매기기result={} #레벨에 따른 노드들위치
def inorder(node,level=1): #중위순회 global position if node.left !=-1:
inorder(tree[node.left],level+1) position+=1 #가장왼쪽부터 증가
if level in result: result[level].append(position) else:
result[level]=[position] if node.right != -1:
inorder(tree[node.right],level+1) n=int(input())tree={}
#각 노드의 자기자신,left,right,parent업데이트하기for _ in range(n):
data,left,right=map(int,input().split())
tree[data]=Node(data,left,right,-1)for i in range(1,n+1):
if tree[i].left != -1: tree[tree[i].left].parent=data
if tree[i].right != -1: tree[tree[i].right].parent=data
for i in tree.keys(): if tree[i].parent==-1: root=i break;
inorder(tree[root])answer_idx=1answer=-19for i in sorted(result.keys()):
tmp=max(result[i])-min(result[i]) if tmp>answer: answer_idx=i
answer=tmpprint(answer_idx,answer+1)