이 글에서는 그래프에 존재하는 싱크(sink) 노드의 개수를 구하는 방법을 자세히 알아보겠습니다. 문제는 다음과 같습니다. N개의 노드(1부터 N까지)와 M개의 간선으로 이루어진 방향 비순환 그래프(DAG, Directed Acyclic Graph)가 주어졌을 때, 이 그래프에 몇 개의 싱크 노드가 있는지 찾아야 합니다. 여기서 싱크 노드란 나가는 간선(outgoing edge)이 하나도 없는 노드를 의미합니다. 간단한 예시를 통해 살펴보겠습니다.
입력 : n = 4, m = 2
간선[] = {{2, 3}, {4, 3}}
출력 : 2
싱크 노드를 찾는 간단한 접근법
이 방법의 핵심 아이디어는 매우 직관적입니다. 먼저 그래프의 모든 간선을 순회하면서, 간선이 시작되는 노드(출발 노드)들을 집합(set)에 저장합니다. 집합은 중복을 허용하지 않기 때문에, 간선이 나가는 서로 다른 노드들만 저장됩니다. 즉, 집합에는 '싱크가 아닌 노드'만 모이게 됩니다. 마지막으로 전체 노드 수에서 집합의 크기를 빼면, 곧 싱크 노드의 개수를 얻을 수 있습니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
int main(){
int n = 4; // 노드의 개수
int m = 2; // 간선의 개수
vector<pair<int, int>> edges = {{2, 3}, {4, 3}}; // 첫 번째 노드에서 두 번째 노드로 향하는 간선
set<int> s;
for(int i = 0; i < m; i++){
s.insert(edges[i].first); // 간선이 나가는
// 서로 다른 출발 노드의 값만 저장됨
}
cout << n - s.size(); // 정답 = 전체 노드 수 - 싱크가 아닌 노드 수
return 0;
}
실행 결과
2
코드 설명
이 코드에서는 간선 벡터(edges)를 순회하면서 각 쌍(pair)의 첫 번째 요소, 즉 간선의 출발 노드를 집합에 삽입합니다. 집합은 중복된 값을 저장하지 않으므로, 최종적으로 집합에는 간선이 나가는 서로 다른 노드들만 남게 됩니다. 따라서 전체 노드 수에서 집합의 크기를 빼면 싱크 노드의 개수가 됩니다. 위 프로그램의 시간 복잡도는 O(M)이며, 여기서 M은 그래프에 존재하는 간선의 개수입니다. 간선 목록을 한 번만 순회하면 되기 때문에 매우 효율적인 알고리즘이라고 할 수 있습니다.
마무리
이 글에서는 집합(set)을 활용하여 그래프에 존재하는 싱크 노드의 개수를 선형 시간 복잡도로 구하는 문제를 해결했습니다. 핵심은 '나가는 간선이 있는 노드'를 중복 없이 세고, 이를 전체 노드 수에서 빼는 것입니다. 또한 이 문제를 해결하기 위한 C++ 프로그램과 전체적인 접근 방법도 함께 살펴보았습니다. 동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 구현할 수 있습니다. 이 글이 여러분의 학습에 도움이 되었기를 바랍니다.