백준1991 - 트리순회 (그래프, 재귀) Python

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

해당 문제는 이진트리의 전위 순회 / 중위 순회 / 후위 순회한 결괏값을 출력하는 문제다.

문제에서 해당 순회들이 무엇인지는 설명하고 있기 때문에 추가적인 설명은 하지 않는다.

 

해당 입력값에 따른 그래프 구현은 아래와 같다.

들어오는 문자열을 쪼갠 뒤 root 노드를 key로 설정, 왼쪽 | 오른쪽 자식이 '.'이면 None으로 설정한 뒤  두 자식을 리스트로 하여 value로 설정했다.

def makingGraph (data) :
  _graph = {}
  for _str in data :
    root, left, right = _str.split()
    left = left if left != '.' else None
    right = right if right != '.' else None
    _graph[root] = [left, right]
  return _graph

즉 graph[root][0]은 왼쪽 자식, graph[root][1]은 오른쪽 자식인 셈이다.

 

이후 전위 순회를 하는 코드를 다음과 같이 작성했다.

storage = [[],[],[]]
preOrder(graph, saveNode(storage[0]))

def preOrder(graph, save, node='A') :
  if not node : return
  save(node)
  preOrder(graph, save, graph[node][0])
  preOrder(graph, save, graph[node][1])

전위 순회는 일반적인 DFS(깊이 우선탐색)과 순회 과정이 비슷하기 때문에, 구현 자체는 간단했다.

즉, 순회하는 node를 저장한 뒤, 다음 순회를 이어나가는 방식이다.

 

이때 여기서 나오는 save 함수는 아래와 같은 함수로, 

함수 자체에 리스트(storage) 자체를 지정해두고, 인자값이 들어오면 해당 리스트에 값을 추가하도록 했다.

따라서, 전위 순회에서 등장하는 노드는 stroage[0] 리스트에 추가된다.

def saveNode (storage) :
  return lambda node : storage.append(node)

 

중위 순회와 후위 순회는 다음과 같다.

# 중위 순회
def inOrder (graph, save, node='A') :
  if not node : return
  inOrder(graph, save, graph[node][0])
  save(node)
  inOrder(graph, save, graph[node][1])
  
# 후위 순회
def postOrder(graph, save, node='A') :
  if not node : return
  postOrder(graph, save, graph[node][0])
  postOrder(graph, save, graph[node][1])
  save(node)

중위 순회는 왼쪽 자식 -> 루트 -> 오른쪽 자식 순으로 순회가 이어지기 때문에,

최하위 노드이면서 왼쪽 자식인 노드부터 저장할 수 있도록 했다.

 

후위 순회도 마찬가지로 왼쪽 자식 -> 오른쪽 자식 순으로의 순회가 이어지기 때문에,

끝단 노드에서부터 노드를 저장할 수 있도록 했다.

 

전체 소스 코드

import sys
data_temp = sys.stdin if sys.platform == 'linux' else open('입력.txt', 'r')
input_data = data_temp.read().splitlines()

def solution (data) :
  data.pop(0)
  graph = makingGraph(data)
  storage = [[],[],[]]
  
  preOrder(graph, saveNode(storage[0]))
  inOrder(graph, saveNode(storage[1]))
  postOrder(graph, saveNode(storage[2]))
  
  result = list(map(lambda x : ''.join(x), storage))
  print('\n'.join(result))
  
def makingGraph (data) :
  _graph = {}
  for _str in data :
    root, left, right = _str.split()
    left = left if left != '.' else None
    right = right if right != '.' else None
    _graph[root] = [left, right]
  return _graph

def saveNode (storage) :
  return lambda node : storage.append(node)

def preOrder(graph, save, node='A') :
  if not node : return
  save(node)
  preOrder(graph, save, graph[node][0])
  preOrder(graph, save, graph[node][1])
  
def inOrder (graph, save, node='A') :
  if not node : return
  inOrder(graph, save, graph[node][0])
  save(node)
  inOrder(graph, save, graph[node][1])
  
def postOrder(graph, save, node='A') :
  if not node : return
  postOrder(graph, save, graph[node][0])
  postOrder(graph, save, graph[node][1])
  save(node)
  
solution(input_data)