문제 개요
이 문제에서는 N개의 정수로 이루어진 배열 arr가 주어지며, arr[i]는 그래프의 (i+1)번째 노드가 가진 값을 나타냅니다. 아울러 M개의 간선 쌍이 제공되고, 각 쌍의 u와 v는 간선으로 서로 연결된 두 노드를 의미합니다. 목표는 무방향 그래프를 이루는 모든 연결된 구성 요소(connected component)에서 각각 최솟값을 찾아, 이 값들을 모두 더한 합계를 구하는 프로그램을 작성하는 것입니다. 다른 어떤 노드와도 연결되지 않은 노드는 노드 하나짜리 독립적인 구성 요소로 간주합니다.
문제 이해를 돕는 예시
입력
arr[] = {2, 7, 5, 1, 3}, m = 2
간선: 1 2
4 5
출력
8
설명
위 입력으로 만들어지는 그래프는 다음과 같습니다.
그래프는 두 개의 연결된 구성 요소와 하나의 고립된 노드로 이루어져 있습니다. 각 구성 요소의 최솟값은 다음과 같습니다.
- (노드 1, 노드 2) 구성 요소: min(2, 7) = 2
- (노드 4, 노드 5) 구성 요소: min(1, 3) = 1
- (노드 3) 구성 요소: min(5) = 5
따라서 전체 합계는 2 + 1 + 5 = 8입니다.
해결 접근 방식
이 문제는 DFS(깊이 우선 탐색)나 BFS(너비 우선 탐색) 같은 그래프 순회 기법을 활용하면 효율적으로 해결할 수 있습니다. 절차는 다음과 같습니다.
- 방문 여부를 기록하는 visited 배열을 준비하여, 같은 노드를 중복 방문하지 않도록 합니다.
- 아직 방문하지 않은 노드를 발견하면, 그 노드를 시작점으로 DFS를 수행해 직접적·간접적으로 연결된 모든 노드를 탐색합니다.
- 탐색 과정에서 해당 구성 요소에 속한 노드 값들의 최솟값을 추적합니다.
- 하나의 구성 요소 탐색이 끝날 때마다 구한 최솟값을 sum 변수에 더합니다.
- 모든 노드를 방문하고 나면 sum을 결과로 출력합니다.
각 노드와 간선을 한 번씩만 확인하므로 시간 복잡도는 O(N + M)입니다.
C++ 구현 예제
위 접근 방식을 구현한 프로그램입니다. 재귀 호출 사이에서 최솟값이 올바르게 유지되도록 참조(&)로 전달하는 점에 유의하세요.
#include <bits/stdc++.h>
using namespace std;
const int N = 100;
vector<int> graph[N];
bool visited[N];
void dfs(int node, int arr[], int &minimum){
minimum = min(minimum, arr[node]);
visited[node] = true;
for (int i : graph[node]) {
if (!visited[i])
dfs(i, arr, minimum);
}
}
void createEdge(int u, int v){
graph[u - 1].push_back(v - 1);
graph[v - 1].push_back(u - 1);
}
int minSum(int arr[], int n){
int sum = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
int minimum = arr[i];
dfs(i, arr, minimum);
sum += minimum;
}
}
return sum;
}
int main(){
int arr[] = {2, 7, 5, 1, 3};
createEdge(1, 2);
createEdge(4, 5);
int n = sizeof(arr) / sizeof(arr[0]);
cout << "무방향 그래프의 모든 연결 요소에서 최솟값들의 합은 ";
cout << minSum(arr, n);
return 0;
}
실행 결과
무방향 그래프의 모든 연결 요소에서 최솟값들의 합은 8