[SWEA] 1231. 중위순회 - Python

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV140YnqAIECFAYD 

SW Expert Academy

< 📝 문제 >
다음은 특정 단어(또는 문장)를 트리 형태로 구성한 것으로, in-order 형식으로 순회하여 각 노드를 읽으면 원래 단어를

 

알 수 있다고 한다.

위 트리를 in-order 형식으로 순회할 경우 SOFTWARE 라는 단어를 읽을 수 있다.

< ❓ 생각 >

제약 사항에 완전 이진 트리 형식

노드 주어지는 순서는 번호 순서대로

 

1. 완전 이진 트리이고 순서대로 삽입되므로 자식노드번호 활용 X

inorder 함수로 단어 완성 후 출력

 

2. 자식 노드 번호 활용

입력값의 길이가 3이면 왼쪽 자식만 있음, 4면 오른쪽 자식도 있음

tree에 알파벳 삽입

왼쪽 자식 노드 번호, 오른쪽 자식 노드 번호 체크

inorder 함수로 읽어내기

 

< 💻 코드 >

1. 자식 노드 번호 활용 X

def in_order(n):
    global word
    if n <= N:
        # 왼쪽 자식
        in_order(n*2)
        # 알파벳
        word += arr[n-1][1]
        # 오른쪽 자식
        in_order(n*2+1)

for tc in range(1,11):
    # 트리가 갖는 정점의 총 수
    N = int(input())
    # 정점 번호, 해당 정점 알파벳, 왼쪽 자식, 오른쪽 자식
    arr = [input().split() for _ in range(N)]
    
    # 단어
    word = ''
    in_order(1)
    print(f'#{tc} {word}')

2. 자식 노드 번호 활용

def in_order(v):
	# 0번 정점이 없으므로, 0번은 자식이 없는 경우를 표시
    if v:
    	# 왼쪽 자식
        in_order(ch1[v])
        print(tree[v],end='') # visit(v)
        # 오른쪽 자식
        in_order(ch2[v])

# 완전 이진 트리
for tc in range(1,11):
    # 정점의 총 수
    last = int(input())

    # 완전 이진 트리 만들기
    tree = [0]*(last+1)
    # 왼쪽 자식
    ch1 = [0]*(last+1)
    # 오른쪽 자식
    ch2 = [0]*(last+1)

    for _ in range(last):
        s = input().split()
        # s[0] : 노드 번호, s[1] : 알파벳
        tree[int(s[0])] = s[1]
        
        # 왼쪽 자식이 있다면
        if len(s) >= 3:
        	# s[2] : 왼쪽 자식 노드 번호
            ch1[int(s[0])] = int(s[2])
            
        # 오른쪽 자식이 있다면
        if len(s) == 4:
        	# s[3] : 오른쪽 자식 노드 번호
            ch2[int(s[0])] = int(s[3])
            
    print(f'#{tc} ',end='')
    in_order(1)
    print()

< ❗ 느낀 점 >

완전 이진 트리이고 순서대로 삽입되므로 자식 노드 번호를 생각하지 않는 편이 간단했다.