[코드 인터뷰 대비 시리즈 #4] 트리(Tree)와 그래프(Graph) 문제 접근 패턴 완벽 정리

여러분, 코딩 인터뷰에서 트리와 그래프 문제는 난이도를 조정하기 매우 좋은 자료구조 문제 유형으로 꼽힙니다. 트리나 그래프는 노드(Node)와 엣지(Edge)로 구성되며, 선형적인 배열·문자열·스택·큐와 달리, 비선형적이고 연결 구조를 갖기 때문에 문제에서 다루는 패턴이 훨씬 다양하고 깊습니다. 이번 글에서는 트리와 그래프 문제를 만났을 때 어떤 사고 과정을 거쳐 해결할 수 있는지, 주요 패턴들(트리 순회, 레벨 순회, 최소/최대 깊이, 직경 계산, 그래프 사이클 검출, 위상 정렬, 최단 경로 알고리즘, MST 등)을 단계별로 하나하나 꼼꼼히 살펴보겠습니다.

이 글을 읽고 나면, 여러분은 트리와 그래프 문제를 처음 보고도 당황하지 않고, "아, 이 문제는 DFS/BFS로 O(V+E)에 해결 가능하겠군", "최단 경로는 Dijkstra를 써볼까, BFS로 충분할까?", "위상 정렬로 순서를 결정할 수 있네" 같은 식으로 빠르게 접근 방법을 결정하고, 면접관에게 이 로직을 어떻게 논리적으로 설명하면 좋을지까지 명확히 감이 잡힐 것입니다.

1. 트리 문제 접근의 기초: 다양한 순회(Traversal)와 기초 연산

트리 문제를 받았을 때 가장 기본이 되는 것은 트리 순회입니다. 트리는 사이클이 없는 연결 그래프의 한 형태이므로, DFS/BFS로 손쉽게 순회할 수 있고, 전위·중위·후위 순회나 레벨 순회(level order traversal) 같은 패턴이 자주 등장합니다.

주요 패턴:

1. 트리 순회(전위·중위·후위) 기본 문제:
   주어진 트리에서 전위/중위/후위 순회를 구현하거나, 순회 결과로부터 트리를 복원하는 문제가 종종 나옵니다. 예를 들어 Baekjoon에서 "트리 순회" 관련 문제가 있다면, 전위 순회는 (현재 노드 처리 → 왼쪽 → 오른쪽), 중위 순회는 (왼쪽 → 현재 → 오른쪽), 후위 순회는 (왼쪽 → 오른쪽 → 현재) 순서로 처리한다는 정의를 알고 있어야 합니다.
   면접장에서 이러한 순회 방식을 언급할 때는 "전위 순회를 통해 루트를 가장 먼저 처리하고, 중위 순회와 결합해 트리를 재구성할 수도 있습니다"라고 말할 수 있고, "이 과정은 DFS 기반으로 구현하며, 각 순회는 O(N) 시간에 가능하고 추가 메모리는 재귀 호출 스택 정도가 필요합니다"라고 복잡도를 언급하면 좋습니다.
2. 최소 깊이, 최대 깊이 계산:
   트리의 최대 깊이(max depth)나 최소 깊이(min depth) 계산 문제는 트리 문제에서 매우 빈출됩니다. 예를 들어 LeetCode "Maximum Depth of Binary Tree" 문제에서 DFS 또는 BFS를 사용해 깊이를 계산합니다.
   단계별 사고 과정:
   
   • 문제: 이진 트리의 최대 깊이를 구하라.
   • 아이디어: 루트부터 시작해 DFS로 왼쪽/오른쪽 서브트리 깊이를 구하고, 그 중 큰 값에 1을 더하면 루트의 최대 깊이가 됩니다. O(N) 시간, O(h) 공간(h는 트리 높이).
   • 코너 케이스: 빈 트리면 깊이는 0, 단일 노드면 깊이는 1.
   면접장에서 "DFS 한 번으로 O(N)에 최대 깊이 계산 가능하며, 재귀 호출로 높이 계산 시 서브트리 깊이를 합치는 로직을 명확히 설명"하면 좋습니다.
3. 트리 직경(Diameter) 계산:
   트리 직경은 가장 긴 경로의 길이를 의미합니다. 전형적으로 DFS를 두 번 쓰거나, 한 번의 재귀에서 (왼쪽 서브트리 높이 + 오른쪽 서브트리 높이)을 업데이트하며 최대 직경을 찾을 수 있습니다.
   단계별 사고 과정:
   
   • 문제: 이진 트리의 직경을 구하라. (직경 = 가장 긴 루트 간 경로)
   • 아이디어: DFS로 각 노드에서 왼쪽/오른쪽 서브트리 높이를 구하고, (왼쪽 높이 + 오른쪽 높이)로 직경 후보를 갱신. 전체 과정 O(N).
   • 면접에서 "노드마다 왼/오른쪽 높이 계산 후 직경 후보 갱신, 최종 전역 변수에 최대값 저장" 같은 구현 상세를 언급하세요.

LeetCode "Diameter of Binary Tree" 문제로 연습 가능합니다.

2. 트리 레벨 순회(Level Order Traversal)와 BFS

레벨 순회는 큐(Queue)를 이용해 같은 레벨의 노드들을 묶어서 처리하는 기법입니다. 이때 BFS를 사용합니다.

단계별 사고 과정 (레벨 순회):

1. 문제: 이진 트리를 레벨별로 순회해 각 레벨의 노드 목록을 반환하라.
2. 아이디어: 큐에 루트를 넣고, 큐에서 뽑을 때마다 그 레벨에 속한 노드들을 모두 처리한 뒤, 그 다음 레벨 노드들을 큐에 넣는다. O(N) 시간, O(N) 공간.
3. 코너 케이스: 빈 트리일 경우 빈 리스트 반환. 단일 노드면 레벨이 1개뿐.
4. 면접에서 "큐를 사용해 레벨 단위로 노드를 처리, 각 단계에서 현재 큐 크기만큼 노드를 뽑아 해당 레벨 노드 목록 생성"이라고 설명할 수 있습니다.

LeetCode "Binary Tree Level Order Traversal" 문제로 연습해보세요.

3. 그래프 문제 접근: DFS/BFS 기반 패턴

그래프는 노드와 엣지로 이루어진 일반화된 구조입니다. 트리는 사이클 없는 연결 그래프의 특수케이스지만, 그래프는 사이클이 있을 수도 있고, 여러 컴포넌트가 존재할 수도 있습니다. 면접에서 그래프 문제는 DFS/BFS를 통한 연결성 탐색, 사이클 검출, 위상 정렬, 최단 경로 계산 등으로 주로 출제됩니다.

대표적 패턴:

• 연결 컴포넌트(Connected Components) 찾기:
  그래프가 주어졌을 때, 몇 개의 연결 컴포넌트로 나뉘는지 계산하거나, 특정 노드가 속한 컴포넌트의 크기를 구하는 문제는 매우 빈번합니다. 이 때 DFS나 BFS로 방문하지 않은 노드를 발견할 때마다 그 노드를 시작점으로 탐색하여 해당 컴포넌트의 모든 노드를 방문합니다.
  • O(V+E) 시간, V는 노드 수, E는 엣지 수.
  • 코너 케이스: 빈 그래프(V=0), 엣지 없는 그래프(각 노드가 컴포넌트 하나씩) 처리.
  • 면접에서 "DFS/BFS 한 번으로 컴포넌트 하나를 탐색, 방문 체크 후 다음 미방문 노드에서 또 DFS/BFS"라고 설명하세요.

Baekjoon "연결 요소의 개수" 문제나 Codeforces 그래프 기초 문제로 연습해보면 좋습니다.

• 사이클(Cycle) 검출:
  방향 그래프에서 사이클 검출은 위상 정렬 전 단계로 자주 등장합니다. 무방향 그래프 사이클 검출은 DFS로, 방문 중인 노드를 다시 방문하면 사이클 존재. 방향 그래프는 DFS 중 "현재 탐색 중인 경로"에 있는 노드를 재방문하면 사이클.
  단계별 사고 과정:
  
  • 문제: 방향 그래프 사이클 검출.
  • 아이디어: DFS로 탐색 중인 노드를 추적하는 상태 배열(방문X, 방문 중, 방문 완료) 3가지 상태 관리. 방문 중 상태 노드를 다시 방문하면 사이클.
  • 면접에서 "색 배열(white, gray, black) 또는 방문중/완료 표시로 사이클 감지. O(V+E) 시간"이라고 설명하세요.
• 위상 정렬(Topological Sort):
  방향 비순환 그래프(DAG)에 대해 순서 정하는 문제(예: 과목 선후수 관계)를 위상 정렬로 O(V+E)에 해결. 큐나 스택을 이용한 구현, 진입 차수(indegree) 계산, indegree 0인 노드 큐에 넣고 빼면서 순서 결정.
  단계별 사고 과정:
  
  • 문제: 과목/작업을 DAG 형태로 표현, 모든 일을 하는 순서를 찾으라.
  • 아이디어: 모든 노드의 indegree 계산, indegree 0인 노드를 큐에 넣고, 큐에서 빼면서 그 노드와 연결된 엣지 제거, 새로 indegree 0된 노드 추가.
  • 코너 케이스: 사이클 있으면 위상 정렬 불가. 이때 큐에서 꺼낸 노드 수가 V보다 적게 끝나면 사이클이라는 에러 반환.
  • 면접 시 "위상 정렬은 O(V+E)로 순서 결정, 사이클 시 실패"라고 명확히 언급.

LeetCode "Course Schedule" 문제나 Programmers의 위상 정렬 문제로 연습해보세요.

4. 최단 경로 알고리즘: BFS, Dijkstra, Bellman-Ford

그래프 문제에서 최단 경로 관련 문제가 나오면, 그래프 특성과 엣지 가중치 여부를 먼저 확인하세요.

• 무가중치 그래프에서 최단 경로: BFS로 O(V+E)에 가능.
• 가중치(비음수) 그래프에서 단일 출발점 최단 경로: Dijkstra 알고리즘 사용. 우선순위 큐 사용, O(E log V).
• 모든 쌍 최단 경로: Floyd-Warshall O(V^3), 일반적으로 대형 그래프엔 비효율적. 면접에서 자료구조 문제 중심인 경우 Floyd-Warshall을 직접 구현하기보다는 알고 있다는 정도만 언급하는 것도 좋습니다.

면접 예시 상황: “가중치 있는 그래프에서 출발점으로부터 모든 노드 최단 거리를 구하라.”

• 아이디어: Dijkstra 사용. 우선순위 큐에 (거리, 노드) 넣고, 거리가 최소인 노드부터 꺼내 주변 엣지 완화(relaxation).
• 코너 케이스: 그래프가 비연결이면 특정 노드 도달 불가 시 에러 또는 INF 값 유지.
• 면접에서 “Dijkstra를 통해 O(E log V)로 최단 경로 계산, 음수 가중치 있으면 Bellman-Ford나 SPFA 고려”라고 논리적으로 말하세요.

LeetCode "Network Delay Time", Baekjoon "다익스트라" 문제, Codeforces 그래프 최단 경로 문제로 연습 가능합니다.

5. MST(최소 신장 트리) 개념 응용

MST 문제는 Kruskal이나 Prim 알고리즘으로 해결 가능합니다. 이는 그래프를 최소 비용으로 모두 연결하는 문제이고, O(E log E) 또는 O(E log V)에 해결. 면접관이 MST를 묻는다면 “Kruskal로 간선 정렬 후 유니온파인드로 MST 구성” 혹은 “Prim으로 특정 노드부터 시작해 우선순위 큐로 최소 간선 선택”을 언급하면 됩니다.

코너 케이스: 그래프가 이미 연결되어 있는지, 아니면 MST 구성이 불가능한지 검사해야 합니다. MST가 불가능하면 에러 반환. 면접 시 "유니온파인드로 집합 관리, 모든 노드가 하나의 집합으로 합쳐질 때까지 반복" 등의 로직 언급.

Baekjoon MST 문제나 Codeforces MST 문제를 풀면서 Kruskal/Prim 연습해보세요.

6. 조건부 처리, 비동기 처리, 로깅, 에러 처리, Ranges 응용

트리/그래프 문제에서도 모던 C++ 기능을 활용할 여지가 많습니다. 예를 들어, 위상 정렬 중 사이클 검출 시 std::expected로 에러 반환하고, 로깅(std::format)을 통해 BFS/DFS 과정에서 방문 순서를 출력하거나, coroutine을 통해 대규모 그래프를 비동기로 탐색(예: 큰 데이터를 스트리밍받으며 실시간으로 BFS)할 수도 있다고 면접에서 언급해보세요. 이런 확장성을 보여주면 면접관에게 깔끔한 코드 관리 능력과 미래 확장 가능성을 시사할 수 있습니다.

또한 Ranges를 사용해 다수 테스트 케이스에 대해 동일한 그래프 로직을 연속 적용하거나, 그래프를 특정 조건으로 필터링한 뒤 탐색하는 과정도 파이프라인 방식으로 표현할 수 있습니다.

7. 예제 문제를 통한 실전 연습

• 트리 최대 깊이 문제: LeetCode "Maximum Depth of Binary Tree"로 DFS/BFS 방식 연습, 코너 케이스 처리.
• 트리 직경 문제: "Diameter of Binary Tree" (LeetCode)로 DFS 통한 직경 계산 확인.
• 그래프 연결 요소 문제: Baekjoon "연결 요소의 개수" 문제로 DFS/BFS 연습.
• 위상 정렬 문제: LeetCode "Course Schedule" 문제로 위상 정렬과 사이클 검출 연습.
• 최단 경로 문제(Dijkstra): Baekjoon "최단경로" 문제로 Dijkstra 알고리즘 구현 연습.

각 문제를 풀 때 시간복잡도, 공간복잡도, 코너 케이스, 힌트 요청 전략, 커뮤니케이션 포인트를 정리해두면 인터뷰장에서 즉각적으로 사고를 표현하는 데 도움이 됩니다.

8. 면접장에서의 사고 과정 표현 예시

“이 그래프에서 사이클이 있는지 판별하고, 있다면 일부 노드 순서를 결정할 수 없는지 알려주세요”라는 문제를 받았다고 가정해봅시다.

1. 접근 아이디어 언급:
   “사이클 검출을 위해 DFS를 이용할 수 있습니다. 노드 상태를 unvisited, visiting, visited 세 가지로 관리해, DFS 도중 visiting 상태의 노드를 다시 방문하면 사이클 존재로 판단하겠습니다.”
2. 단계별 구현 로직 설명:
   “각 노드에 대해 unvisited면 DFS 호출, DFS 진입 시 visiting으로 변경, 탐색 끝나면 visited로 변경. 탐색 중 visiting 상태 노드를 재방문하면 사이클. O(V+E) 시간 복잡도로, 모든 노드를 한 번씩 탐색하며 사이클을 파악할 수 있어요.”
3. 코너 케이스 언급:
   “빈 그래프(V=0)면 당연히 사이클 없음, 단일 노드 무엣지도 사이클이 없는 경우 그냥 O(1)로 처리. 유방향 그래프는 이 방식으로 사이클 쉽게 체크 가능.”
4. 로깅이나 에러 처리 옵션 제안:
   “만약 사이클 발생 시 std::expected를 통해 “Cycle detected” 에러를 반환하고, 로깅(std::format)을 사용해 어느 노드에서 사이클이 발견됐는지 콘솔에 출력할 수도 있습니다.”

이렇게 구체적으로 설명하면 면접관에게 여러분의 사고 과정, 코드 구현 전략, 문제 해결 능력을 선명하게 각인시킬 수 있습니다.

마무리

이번 글에서는 트리와 그래프 문제에 집중해 DFS/BFS를 통한 연결성 탐색, 트리 순회, 최대/최소 깊이 계산, 직경, 사이클 검출, 위상 정렬, 최단 경로 알고리즘(Dijkstra) 등 다양한 패턴을 단계별로 상세히 설명했습니다. 또, 조건부 처리나 비동기 처리, 로깅 등을 통해 문제 확장 가능성을 언급함으로써 문제 해결 능력을 넘어선 코드 관리 및 확장성에 대한 사고도 제안해드렸어요.

이제 여러분은 트리/그래프 문제를 받았을 때, "이 문제는 BFS로 레벨 순회하면 O(N)에 가능하겠군", "사이클 검출은 DFS 상태 관리로 O(V+E)에 판단 가능하네", "최단 경로는 Dijkstra 적용, O(E log V)로 풀 수 있고, 음수 간선이면 Bellman-Ford 고려해야지"라는 식으로 빠르게 접근법을 확정하고, 면접관에게 논리적으로 설명할 수 있을 겁니다.

이렇게 패턴을 명확히 인지하고, 문제 접근 과정에서 각 단계를 구체적으로 사고하며, 커뮤니케이션 포인트까지 준비한다면 실제 인터뷰 상황에서 트리와 그래프 문제에도 당황하지 않고 침착하게 해결할 수 있을 것입니다.