문제 링크
https://www.acmicpc.net/problem/4256
🕒 Python 풀이시간: 50분
import sys
from collections import deque
input=sys.stdin.readline
def makeTree(rootV,rootI,start,end):
global preorder, inorder
if start>end:
return False
rootIndex=-1
root=-1
for i in range(start,end+1):
if inorder[i]==preorder[0]:
rootIndex=i
root=preorder.popleft()
break
left=makeTree(root,rootIndex,start,rootIndex-1)
right=makeTree(root,rootIndex,rootIndex+1,end)
if left:
graph[root].append((0,left))
if right:
graph[root].append((1,right))
return root
def printPostOrder(tree,root):
if len(graph[root])==0:
print(root,end=' ')
return
for i in range(len(tree[root])):
printPostOrder(tree,tree[root][i][1])
print(root,end=' ')
for tc in range(1,int(input())+1):
n=int(input())
preorder=deque(list(map(int,input().split())))
k=preorder[0]
inorder=list(map(int,input().split()))
graph=[[] for _ in range(n+1)]
makeTree(0,0,0,n-1)
printPostOrder(graph,k)
print()트리 복구: 전위와 중위 순회로 후위 순회 출력하기! 🌳🔄
전위 순회와 중위 순회의 결과물을 가지고 트리를 복구시키고 그 트리를 가지고 후위 순위를 다시 출력하는 문제이다. 처음 접해보는 구현 및 분할 정복 유형이라 처음에는 좀 당황스러웠다.
먼저 접근 방법이 감이 안오기도 하고 전위 순회와 중위 순회 방법을 까먹고 있어서 그림을 한번 그려보면서 방법을 익히고 규칙을 파악하려고 하였다. 전위 순회는 루트 노드부터 오기 때문에 루트노드를 전위 순회에서 앞에서부터 파악하면서 왼쪽인지 오른쪽인지는 중위 순회를 통해 전위 순회에서 찾은 루트 노드를 기준으로 반으로 가르면서 탐색한다는 규칙을 찾았고 이 부분에서 분할 정복이 사용된다는 것을 알았다.
규칙 자체는 단순하였다. 끝에서 더 이상 탐색할 부분이 없으면 False를 리턴해주고 그렇지 않으면 전위순회에서 찾은 루트 노드의 위치를 파악한다. 그 위치를 기준으로 양쪽으로 재귀 함수를 찾아주면 된다. 이 때, False가 리턴되면 그쪽 트리는 존재하지 않기 때문에 값이 있을 경우에만 왼쪽 오른쪽을 해서 붙여준다. 현재 루트까지의 트리가 완성되었으면 현재의 값을 리턴하면 된다.
트리가 복구가 되었다면 PostOrder 방식으로 읽으면 된다. 단순히 안으로 들어가서 읽어오면 되기 때문에 재귀를 통해 간단히 해결할 수 있었다.
이렇게 Python으로 백준의 "트리" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊
