DFS 트리 순회

백준 1991. 트리 순회

DFS로 구현했다.

• 전위: 루트가 우선. 루트 - 왼쪽자식 - 오른쪽자식
• 중위: 왼쪽자식 - 루트 - 오른쪽자식
• 후위: 루트가 마지막. 왼쪽자식 - 오른쪽자식 - 루트

---

코드

def dfs_prefix(node):
    if node == '.':
        return
    print(node, end='')
    dfs_prefix(node_dict[node][0])
    dfs_prefix(node_dict[node][1])

def dfs_infix(node):
    if node == '.':
        return
    dfs_infix(node_dict[node][0])
    print(node, end='')
    dfs_infix(node_dict[node][1])

def dfs_postfix(node):
    if node == '.':
        return
    dfs_postfix(node_dict[node][0])
    dfs_postfix(node_dict[node][1])
    print(node, end='')

N = int(input())
node_dict = {}
for _ in range(N):
    a, b, c = input().split()
    node_dict[a] = [b, c]

dfs_prefix('A')
print()
dfs_infix('A')
print()
dfs_postfix('A')
print()

---

개선 코드

함수를 한 개만 사용하도록 수정할 수 있었다.

prefix = []
infix = []
postfix = []

def dfs(node):
    if node == '.':
        return
    prefix.append(node)
    dfs(node_dict[node][0])
    infix.append(node)
    dfs(node_dict[node][1])
    postfix.append(node)

N = int(input())
node_dict = {}
for _ in range(N):
    a, b, c = input().split()
    node_dict[a] = [b, c]

dfs('A')
print(''.join(prefix))
print(''.join(infix))
print(''.join(postfix))

---

+) 갑작스런 비교

BFS와 DFS는 시간복잡도는 같지만,  공간복잡도의 경우 트리의 너비가 넓을수록 DFS가 유리하고, 깊이가 깊을수록 BFS가 유리하다…