728x90
https://www.acmicpc.net/problem/1991
트리의 전위, 중위, 후위 순회를 코드로 구현하는 문제이다. c++로 코딩하던 버릇이 남아있어 그런지 아스키 코드를 이용했다
원랜 ans 변수에 답을 담는 것이 아닌, visited 배열을 이용해 답을 저장하려고 아스키 코드를 썻는데 결국 그러진 않았다. 굳이..? 라는 생각이 들어서,,
트리의 순회 방법에 대해 알고 있다면 차례대로 구현해주기만 하면 된다. 좀 더 정석적인 풀이 방법이 구글에 검색하면 많이 나오니 참고하시길!
import sys
from collections import deque
#sys.setrecursionlimit(10**6)
input = sys.stdin.readline
def preorder(now):
global ans, visited
if not visited[now]:
visited[now] = True
ans += chr(now+65)
if tree[now][0] != -19:
preorder(tree[now][0])
if tree[now][1] != -19:
preorder(tree[now][1])
return ans
def inorder(now):
global ans,visited
if tree[now][0] != -19:
inorder(tree[now][0])
if not visited[now]:
visited[now] = True
ans += chr(now+65)
if tree[now][1] != -19:
inorder(tree[now][1])
return ans
def postorder(now):
global ans,visited
if tree[now][0] != -19:
postorder(tree[now][0])
if tree[now][1] != -19:
postorder(tree[now][1])
if not visited[now]:
visited[now] = True
ans += chr(now+65)
return ans
def init():
global ans, visited
ans = ''
visited = [False for _ in range(n)]
if __name__ == "__main__":
n = int(input())
tree = [[] for i in range(n)]
init()
for _ in range(n):
root, left, right = map(str,input().split())
tree[ord(root)-65]=[ord(left)-65, ord(right)-65] # .은 -19로 표현
print(preorder(0))
init()
print(inorder(0))
init()
print(postorder(0))
728x90
'알고리즘 > 백준(BOJ)' 카테고리의 다른 글
[백준/파이썬] 1707번 이분 그래프 (0) | 2023.03.04 |
---|---|
[백준/파이썬] 1967번 트리의 지름 (0) | 2023.02.22 |
[백준/파이썬] 25307번 시루의 백화점 구경 (0) | 2023.02.16 |
[백준/파이썬] 1167번 트리의 지름 (0) | 2023.02.15 |
[백준/파이썬] 9461번 파도반 수열 (0) | 2023.02.13 |