C++로 주어진 정점 집합에서 도달 가능한 모든 노드 찾기

무방향 그래프(undirected graph)와 정점 집합이 하나 주어져 있다고 가정해 봅시다. 이때 우리가 해야 할 일은, 주어진 집합에 포함된 모든 정점으로부터 도달 가능한(reachable) 모든 노드를 찾아내는 것입니다.

문제 예시

예를 들어 입력이 아래 그림과 같은 그래프라고 해보겠습니다.

이 경우 출력은 [1, 2, 3]과 [4, 5]가 됩니다. 이는 각각 하나의 연결 요소(connected component)를 나타내며, 같은 컴포넌트 안의 노드들끼리만 서로 도달할 수 있기 때문입니다.

해결 접근 방법

핵심 아이디어는 각 정점에서 BFS(너비 우선 탐색)를 수행하되, 이미 방문한 노드는 다시 탐색하지 않도록 하는 것입니다. 이렇게 하면 동일한 연결 요소에 속한 여러 정점에 대해 탐색 결과를 재사용할 수 있어 효율적입니다.

구체적인 단계는 다음과 같습니다.

nodes := 그래프에 있는 노드의 총 개수
크기가 nodes + 1인 배열 visited를 선언하고 0으로 초기화합니다. (0은 아직 방문하지 않음을 의미)
연결 요소 번호별 탐색 결과를 저장할 맵 m을 하나 정의합니다.
연결 요소 개수를 세는 변수 comp_sum := 0 으로 초기화합니다.
i := 0 부터 i < n 까지 반복하며 다음을 수행합니다.
- u := arr[i]
- 만약 visited[u]가 거짓(false)이라면:
  - comp_sum을 1 증가시킵니다.
  - 노드 u에서 시작하는 그래프 g의 BFS 탐색을 수행하고, 그 결과를 m[visited[u]]에 저장합니다. (BFS 과정에서 방문된 노드들의 visited 값이 현재 연결 요소 번호로 갱신됩니다.)
- m[visited[u]]에 저장된 탐색 결과를 출력합니다.

C++ 구현 예제

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

#include <bits/stdc++.h>
using namespace std;
class Graph{
   public:
      int nodes;
      list<int> *adj_list;
      Graph(int);
      void insert_edge(int, int);
      vector<int> BFS(int, int, int []);
};
Graph::Graph(int nodes) {
   this->nodes = nodes;
   adj_list = new list<int>[nodes+1];
}
void Graph::insert_edge(int u, int v) {
   adj_list[u].push_back(v);
   adj_list[v].push_back(u);
}
vector<int> Graph::BFS(int comp_sum, int src,int visited[]){
   queue<int> queue;
   queue.push(src);
   visited[src] = comp_sum;
   vector<int> reachableNodes;
   while(!queue.empty()) {
      int u = queue.front();
      queue.pop();
      reachableNodes.push_back(u);
      for (auto itr = adj_list[u].begin(); itr != adj_list[u].end(); itr++) {
         if (!visited[*itr]) {
            visited[*itr] = comp_sum;
            queue.push(*itr);
         }
      }
   }
   return reachableNodes;
}
void displayReachableNodes(int n, unordered_map <int, vector<int> > m) {
   vector<int> temp = m[n];
   for (int i=0; i<temp.size(); i++)
      cout << temp[i] << " ";
   cout << endl;
}
void get_all_reachable(Graph g, int arr[], int n) {
   int nodes = g.nodes;
   int visited[nodes+1];
   memset(visited, 0, sizeof(visited));
   unordered_map <int, vector<int> > m;
   int comp_sum = 0;
   for (int i = 0 ; i < n ; i++) {
      int u = arr[i];
      if (!visited[u]) {
         comp_sum++;
         m[visited[u]] = g.BFS(comp_sum, u, visited);
      }
      cout << "Reachable Nodes from " << u <<" are\n";
      displayReachableNodes(visited[u], m);
   }
}
int main() {
   int nodes = 5;
   Graph g(nodes);
   g.insert_edge(1, 2);
   g.insert_edge(2, 3);
   g.insert_edge(4, 5);
   int arr[] = {2, 4, 1};
   int n = sizeof(arr)/sizeof(int);
   get_all_reachable(g, arr, n);
}

입력

g.insert_edge(1, 2);
g.insert_edge(2, 3);
g.insert_edge(4, 5);

출력

Reachable Nodes from 2 are
2 1 3
Reachable Nodes from 4 are
4 5
Reachable Nodes from 1 are
2 1 3

동작 원리 및 시간 복잡도

위 코드에서 visited 배열은 단순한 방문 여부가 아니라 노드가 속한 연결 요소의 번호를 저장한다는 점이 중요합니다. 따라서 이미 탐색된 연결 요소에 속한 정점(예: 마지막에 처리되는 노드 1)에 대해서는 새로 BFS를 수행하지 않고, 이전에 맵에 저장해 둔 결과를 바로 꺼내 출력할 수 있습니다.

시간 복잡도는 각 노드와 간선이 최대 한 번씩만 탐색되므로 O(V + E)입니다. 여기서 V는 정점의 수, E는 간선의 수입니다. 공간 복잡도 역시 인접 리스트, 방문 배열, 결과 저장용 맵 때문에 O(V + E)입니다.