[백준] 1991 - 트리 순회

이 문제는 어려워서 정리 한다기 보다 인접리스트로 그래프를 만드는 것을 처음 접해서 기록 및 정리를 위해 작성한다.

 

 

https://www.acmicpc.net/problem/1991

1991번: 트리 순회

 

---

처음 인접리스트를 배열로 구현한 코드

from sys import stdin as s

s = open('input.txt','rt')

n = int(s.readline())


graph = [[] for _ in range(n+1)]



def preorder(num):
    if num >=0:
        print(chr(num+65),end='')
        preorder(graph[num][0])
        preorder(graph[num][1])     

def inorder(num):
    if num >=0:
        inorder(graph[num][0])
        print(chr(num+65),end='')
        inorder(graph[num][1])        

def postorder(num):
    if num >=0:
        postorder(graph[num][0])
        postorder(graph[num][1])        
        print(chr(num+65),end='')


for i in range(n):
    x , lo1,lo2 = list(map(str,s.readline().rstrip().split()))
    graph[ord(x) - 65].append(ord(lo1) - 65)
    graph[ord(x) - 65].append(ord(lo2) - 65)



preorder(0)
print()
inorder(0)
print()
postorder(0)

 

인접리스트 재 구현

 

from sys import stdin as s

s = open('input.txt','rt')

n = int(s.readline())

graph = {}


for i in range(n):
    x , lo1,lo2 = list(map(str,s.readline().rstrip().split()))
    graph[x] = [lo1,lo2]


def preorder(num):
    if num != ".":
        print(num, end='')
        preorder(graph[num][0])
        preorder(graph[num][1])     

def inorder(num):
    if num != ".":
        inorder(graph[num][0])
        print(num, end='')
        inorder(graph[num][1])        

def postorder(num):
     if num != ".":
        postorder(graph[num][0])
        postorder(graph[num][1])        
        print(num, end='')


preorder('A')
print()
inorder('A')
print()
postorder('A')

 

아래의 방법으로 구하는 것이 아스키코드를 이용안하고 바로 인덱스 값으로 찾을 수 있어서 코딩 문제를 풀 때 훨씬 효율적일 것 같다.