순회 알고리즘(Traversal Algorithms)

개요

순회 알고리즘(Traversal Algorithms)은 트리(Tree), 그래프(Graph)와 같은 비선형 자료구조 내의 모든 노드(또는 정점)를 체계적으로 방문하는 방법이다. 순회는 구조의 전체 상태를 파악하거나 특정 노드 검색, 경로 탐색, 연산 수행에 필수적이다. 이 글에서는 트리 순회와 그래프 순회를 중심으로 다양한 순회 알고리즘의 개념, 구현 방식, 시간 복잡도 및 활용 사례를 정리한다.

---

1. 개념 및 정의

순회(Traversal)는 자료구조에 저장된 데이터를 하나씩 방문하며 특정 작업(출력, 계산 등)을 수행하는 과정이다. 선형 구조는 단순 순차 탐색으로 충분하지만, 트리나 그래프는 분기 구조를 갖기 때문에 다양한 방식의 순회가 존재한다.

---

2. 트리 순회(Tree Traversal)

순회 방식	방문 순서	구현 방식
전위 순회 (Preorder)	루트 → 왼쪽 → 오른쪽	루트 먼저 처리 (DFS 계열)
중위 순회 (Inorder)	왼쪽 → 루트 → 오른쪽	이진 탐색 트리 정렬 효과
후위 순회 (Postorder)	왼쪽 → 오른쪽 → 루트	하위 노드 먼저 처리
레벨 순회 (Level Order)	위에서 아래로, 왼쪽에서 오른쪽	BFS 기반 순회

트리 구조에서는 순회 방식에 따라 처리 결과가 크게 달라진다.

---

3. 그래프 순회(Graph Traversal)

알고리즘	개념	구현 방식	시간 복잡도
DFS (Depth-First Search)	한 방향으로 깊게 탐색	재귀/스택 사용	O(V + E)
BFS (Breadth-First Search)	인접 노드부터 넓게 탐색	큐 사용	O(V + E)

그래프는 방향성, 가중치, 연결성에 따라 순회 방식과 처리 로직이 달라진다.

---

4. DFS vs BFS 비교

항목	DFS	BFS
구조	깊이 우선	너비 우선
자료구조	스택, 재귀	큐
경로 탐색	임의 경로 찾기	최단 경로 찾기 (무가중치)
메모리 사용	상대적으로 적음	큐로 인해 많을 수 있음
사용 예	백트래킹, 위상 정렬	네트워크 탐색, 레벨 기반 문제

문제 특성과 자료구조 형태에 따라 적합한 순회 방법이 달라진다.

---

5. 트리 순회 구현 예시 (Python)

# 이진 트리 노드 정의
class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

# 중위 순회
def inorder(node):
    if node:
        inorder(node.left)
        print(node.key, end=' ')
        inorder(node.right)

순회 알고리즘은 대부분 재귀적으로 구현되며, 스택을 이용한 반복 구현도 가능하다.

---

6. 활용 사례 및 고려사항

분야	순회 방식	활용 예시
컴파일러	후위 순회	구문 트리 계산
탐색 알고리즘	DFS	퍼즐 탐색, 백트래킹
네트워크 분석	BFS	레벨 기반 최단 거리 탐색
이진 탐색 트리	중위 순회	오름차순 출력
인공지능	DFS/BFS	상태공간 탐색, 최적 경로 추적

탐색 대상 구조의 형태와 문제 요구 조건을 고려한 순회 방식 선택이 중요하다.

---

7. 결론

순회 알고리즘은 트리와 그래프와 같은 복잡한 자료구조에서 데이터를 효과적으로 처리하기 위한 핵심 기술이다. 전위/중위/후위/레벨 순회는 트리 중심의 연산에, DFS/BFS는 그래프 기반 탐색에 최적화되어 있으며, 알고리즘과 자료구조의 궁합을 이해하고 적절히 활용할 수 있는 능력이 중요하다. 실무 문제 해결과 알고리즘 최적화를 위해 순회 방식에 대한 깊은 이해는 필수적이다.