입사 코딩테스트 트리와 그래프 완벽 이해: DFS BFS 탐색부터 이진트리까지

입사 코딩테스트를 준비할 때 가장 막히는 부분이 무엇인가 물으면, 많은 사람들이 트리와 그래프 문제를 꼽습니다. 처음엔 둘의 차이도 불명확하고 어디서부터 시작해야 할지 막막하죠. 하지만 핵심 패턴만 파악하면 오히려 점수를 따기 가장 좋은 영역입니다. 오늘은 그래프와 트리의 기초부터 실전 탐색 알고리즘인 DFS, BFS까지 완벽하게 정리해 보겠습니다.

트리와 그래프, 명확한 차이점 비교

많은 분이 둘을 완전히 다른 개념으로 생각하곤 하는데, 사실 트리는 그래프의 특수한 형태입니다. 연결 방식과 제약 조건의 차이가 핵심입니다.

방향성	방향, 무방향 모두 가능	방향 그래프 (부모→자식)
순환 (Cycle)	순환 가능	비순환 (Cycle 없음)
루트 노드	없음	반드시 1개 존재
부모-자식	없음	계층적 관계 (1:N)

이 차이를 아는 것이 왜 중요할까요? 문제에서 "트리"라고 명시되면 "순환이 없다"는 조건을 활용해 훨씬 효율적이고 깔끔한 로직을 짤 수 있기 때문입니다.

코딩테스트 트리와 그래프 자료구조

효율적인 그래프 구현: 인접 행렬 vs 인접 리스트

그래프 문제를 풀 때 가장 먼저 할 일은 데이터를 메모리에 어떻게 저장할지 정하는 것입니다.

① 인접 행렬 (Adjacency Matrix)

2차원 배열을 사용합니다. 노드가 N개일 때 N x N 크기의 배열이 필요합니다.

• 장점: 노드 i와 j의 연결 여부를 O(1)에 즉시 확인 가능.
• 단점: 노드 수에 비해 간선이 적을 경우 메모리 낭비가 심함.

② 인접 리스트 (Adjacency List)

각 노드에 연결된 노드들만 목록으로 관리합니다. 코딩테스트에서 가장 추천하는 방식입니다.

• 장점: 간선(E)의 개수만큼만 메모리를 사용하므로 효율적임 (O(V + E)).
• 단점: 두 노드의 연결 확인을 위해 리스트를 순회해야 함.

# 인접 리스트 방식 (Python 예시)

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

graph[i].append(j) # 노드 i에서 j로 가는 간선 추가

탐색 알고리즘의 핵심: DFS와 BFS

그래프 탐색은 결국 DFS(깊이 우선)와 BFS(너비 우선) 중 하나를 선택하는 싸움입니다.

🔍 DFS (Depth-First Search)

한 우물만 끝까지 파는 방식입니다. 미로 탐색처럼 갈림길이 나오면 일단 한 방향으로 쭉 가보고, 막히면 되돌아옵니다. 재귀 함수(Recursion)로 구현할 때 가장 깔끔합니다.

• 활용: 모든 경로 탐색, 순환(Cycle) 감지, 위상 정렬.
• 주의: 이미 방문한 노드를 다시 가지 않도록 visited 처리가 필수입니다.

🌐 BFS (Breadth-First Search)

가까운 곳부터 먼저 훑는 방식입니다. 큐(Queue)를 사용하며, 최단 경로 문제에 최적화되어 있습니다.
[attachment_0](attachment)

• 활용: 가중치 없는 그래프에서의 최단 거리, 레벨별 탐색.
• 주의: 큐에서 뺄 때가 아니라 큐에 넣을 때 방문 체크를 해야 중복 방문을 막을 수 있습니다.

코딩테스트 트리 그래프 탐색 알고리즘

이진 트리 순회 (Pre/In/Post-order)

이진 트리는 자식이 최대 2개이므로 방문 시점에 따라 세 가지 순회로 나뉩니다. 이는 트리 구조를 다루는 문제의 기초가 됩니다.

• 전위 순회 (Preorder): 부모 → 왼쪽 → 오른쪽 (루트부터 작업 처리)
• 중위 순회 (Inorder): 왼쪽 → 부모 → 오른쪽 (이진 탐색 트리 오름차순 출력)
• 후위 순회 (Postorder): 왼쪽 → 오른쪽 → 부모 (자식 노드 삭제 후 부모 삭제 시)

실전 코딩테스트 합격 팁

1. 최단 거리 단어가 보이면 일단 BFS를 떠올리세요.
2. 모든 경우의 수나 경로의 특징을 기록해야 한다면 DFS가 유리합니다.
3. 그래프 문제를 풀기 전, 반드시 손으로 노드와 간선을 그려보세요. 시각화가 정답률을 높입니다.

트리와 그래프는 처음엔 낯설지만, 반복해서 문제를 풀다 보면 정해진 패턴이 보입니다. 오늘 정리한 개념을 바탕으로 백준이나 프로그래머스의 기초 문제를 풀어보시길 추천드립니다!

BFS·DFS 알고리즘 직관적 이해와 코딩테스트 실전 활용법