Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 그래프가 유효한 트리인지 판별하는 방법

문제 개요

0부터 n-1까지 번호가 매겨진 n개의 노드와 무방향 간선 목록 [u, v]가 주어졌을 때, 이 간선들이 하나의 유효한 트리(valid tree)를 이루는지 확인하는 함수를 작성해야 합니다.

예를 들어 n = 5이고 edges = [[0,1], [0,2], [0,3], [1,4]]라면, 모든 노드가 연결되어 있고 사이클이 없으므로 출력은 true입니다.

유효한 트리의 조건은 다음 두 가지입니다.
① 그래프에 사이클이 존재하지 않아야 합니다.
② 모든 노드가 하나의 연결 요소(connected component)에 속해 있어야 합니다.

풀이 접근 방식: DFS 활용

깊이 우선 탐색(DFS)을 사용하여 사이클 여부와 연결성을 동시에 검사할 수 있습니다. 각 노드의 방문 상태를 세 가지 값으로 관리하는 것이 핵심입니다.

  • 0: 아직 방문하지 않음
  • 2: 현재 DFS 경로상에 있음(탐색 진행 중)
  • 1: 탐색 완료

dfs() 함수의 동작 순서

  1. dfs(node, par, graph, visited) 함수를 정의합니다. par는 부모 노드를 의미합니다.
  2. visited[node]가 1이면 이미 처리된 노드이므로 true를 반환합니다.
  3. visited[node]가 2이면 탐색 중인 노드를 다시 만난 것이므로 사이클이 존재 → false를 반환합니다.
  4. visited[node]를 2로 설정하고 ret = true로 초기화합니다.
  5. node에 인접한 모든 노드를 순회하며, 부모 노드(par)가 아닌 경우 재귀적으로 dfs()를 호출하고 결과를 ret에 AND 연산으로 누적합니다.
  6. 탐색이 끝나면 visited[node]를 1로 변경하고 ret을 반환합니다.

메인 로직의 동작 순서

  1. 크기가 n이고 0으로 초기화된 visited 배열을 생성합니다.
  2. 크기가 n인 인접 리스트(graph)를 만듭니다.
  3. 모든 간선을 순회하며 graph[u]에 v를, graph[v]에 u를 추가하여 양방향으로 연결합니다.
  4. dfs(0, -1, graph, visited)의 결과가 false이면 사이클이 있다는 뜻이므로 false를 반환합니다.
  5. 마지막으로 모든 노드를 확인하여 방문되지 않은(visited[i] == 0) 노드가 하나라도 있으면 그래프가 분리되어 있다는 의미이므로 false를 반환합니다.
  6. 위 조건을 모두 통과하면 true를 반환합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   bool dfs(int node, int par, vector<int> graph[], vector<int>& visited){
      if (visited[node] == 1)
         return true;
      if (visited[node] == 2)
         return false;
      visited[node] = 2;
      bool ret = true;
      for (int i = 0; i < graph[node].size(); i++) {
         if (graph[node][i] != par)
            ret &= dfs(graph[node][i], node, graph, visited);
      }
      visited[node] = 1;
      return ret;
   }
   bool validTree(int n, vector<vector<int>>& edges) {
      vector<int> visited(n, 0);
      vector<int> graph[n];
      for (int i = 0; i < edges.size(); i++) {
         int u = edges[i][0];
         int v = edges[i][1];
         graph[u].push_back(v);
         graph[v].push_back(u);
      }
      if (!dfs(0, -1, graph, visited))
         return false;
      for (int i = 0; i < n; i++) {
         if (!visited[i])
            return false;
      }
      return true;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{0,1},{0,2},{0,3},{1,4}};
   cout << (ob.validTree(5,v));
}

입력

5, {{0,1},{0,2},{0,3},{1,4}}

출력

1

정리

이 알고리즘은 DFS 한 번으로 사이클 검출과 연결성 확인을 모두 수행하므로 시간 복잡도는 O(V + E), 공간 복잡도 역시 O(V + E)입니다. 참고로 Union-Find(서로소 집합) 자료구조를 사용하면 간선을 추가할 때마다 두 노드가 이미 같은 집합에 속하는지 확인하는 방식으로도 동일한 문제를 해결할 수 있습니다.