C++로 네트워크의 중요 연결(Critical Connections) 찾는 방법

문제 개요

n개의 서버가 있다고 가정해 보겠습니다. 서버는 0부터 n-1까지 번호가 매겨져 있으며, 서버 간의 무방향 연결로 하나의 네트워크를 이룹니다. 여기서 connections[i] = [a, b]는 서버 a와 서버 b 사이의 연결을 의미합니다. 모든 서버는 직접적으로 또는 다른 서버를 경유하여 서로 연결되어 있습니다.

이때 중요 연결(critical connection)이란 해당 연결을 제거했을 때 특정 서버가 다른 서버에 도달할 수 없게 되는 연결을 말합니다. 우리의 목표는 네트워크에서 모든 중요 연결을 찾아내는 것입니다.

예를 들어, 입력이 n = 4이고 connection = [[0,1],[1,2],[2,0],[1,3]]이라면,

출력은 [[1,3]]이 됩니다. 서버 0, 1, 2는 서로 순환 구조로 연결되어 있어 어느 하나의 연결이 끊겨도 도달성이 유지되지만, 서버 1과 3 사이의 연결이 끊어지면 서버 3이 고립되기 때문입니다.

해결 접근 방식: Tarjan의 알고리즘

이 문제는 그래프 이론에서 다리(bridge)를 찾는 문제와 동일하며, DFS 기반의 Tarjan 알고리즘으로 O(V+E) 시간 복잡도에 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• disc[]: 각 노드를 DFS로 방문한 순서(발견 시간)를 저장합니다.
• low[]: 해당 노드에서 역방향 간선을 통해 도달할 수 있는 가장 작은 발견 시간을 저장합니다.

간선 (node, x)에 대해 disc[node] < low[x]가 성립하면, x 쪽 서브트리가 node보다 앞선 조상에게 도달할 수 없다는 뜻이므로 해당 간선이 곧 중요 연결(다리)입니다.

알고리즘 단계

• 방문 여부를 관리하기 위한 set(visited)을 정의합니다.
• 배열 disc와 low를 정의하고, 결과를 담을 2차원 배열 ret을 준비합니다.
• dfs() 함수를 정의합니다. 이 함수는 node, 부모 노드 par, 그래프 graph를 인자로 받습니다.
  • node가 이미 방문된 상태라면 즉시 반환합니다.
  • node를 visited에 추가합니다.
  • disc[node]와 low[node]를 현재 time 값으로 설정한 후 time을 1 증가시킵니다.
  • graph[node]의 모든 인접 노드 x에 대해:
    • x가 부모 노드 par와 같다면 건너뜁니다.
    • x를 아직 방문하지 않았다면:
      • dfs(x, node, graph)를 재귀 호출합니다.
      • low[node]를 low[node]와 low[x] 중 최솟값으로 갱신합니다.
      • 만약 disc[node] < low[x]라면, {node, x} 간선을 ret에 추가합니다(중요 연결).
    • x를 이미 방문했다면(역방향 간선):
      • low[node]를 low[node]와 disc[x] 중 최솟값으로 갱신합니다.
• 메인 함수에서는 다음을 수행합니다:
  • disc와 low 배열의 크기를 n + 1로 설정합니다.
  • time을 0으로 초기화합니다.
  • 입력된 연결 정보를 바탕으로 인접 리스트 형태의 그래프를 구성합니다(양방향으로 추가).
  • dfs(0, -1, graph)를 호출한 뒤 ret을 반환합니다.

C++ 구현 예제

아래 구현 예제를 통해 더 잘 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto> > v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << "[";
      for(int j = 0; j <v[i].size(); j++){
         cout << v[i][j] << ", ";
      }
      cout << "],";
   }
   cout << "]"<<endl;
}
class Solution {
   public:
   set<int> visited;
   vector<int> disc;
   vector<int> low;
   int time;
   vector<vector<int> > ret;
   void dfs(int node, int par, vector<int> graph[]) {
      if (visited.count(node))
      return;
      visited.insert(node);
      disc[node] = low[node] = time;
      time++;
      for (int x : graph[node]) {
         if (x == par)
         continue;
         if (!visited.count(x)) {
            dfs(x, node, graph);
            low[node] = min(low[node], low[x]);
            if (disc[node] < low[x]) {
               ret.push_back({ node, x });
            }
         } else{
            low[node] = min(low[node], disc[x]);
         }
      }
   }
   vector<vector<int> > criticalConnections(int n, vector<vector<int> >& v) {
      disc.resize(n + 1);
      low.resize(n + 1);
      time = 0;
      vector<int> graph[n + 1];
      for (int i = 0; i < v.size(); i++) {
         int u = v[i][0];
         int w = v[i][1];
         graph[u].push_back(w);
         graph[w].push_back(u);
      }
      dfs(0, -1, graph);
      return ret;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{0,1},{1,2},{2,0},{1,3}};
   print_vector(ob.criticalConnections(4,v));
}

입력

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

출력

[[1, 3]]

마무리

이 알고리즘은 각 노드와 간선을 한 번씩만 방문하므로 시간 복잡도는 O(V + E), 공간 복잡도 역시 O(V + E)입니다. 네트워크의 단일 장애점(Single Point of Failure)을 찾는 문제로 확장해 생각하면, 서버 클러스터 설계나 통신망 안정성 분석 등 실무에서도 유용하게 활용할 수 있는 개념입니다.