문제
N개의 노드로 이루어진 완전 그래프(모든 노드 쌍 사이에 간선이 존재)가 주어진다. 각 간선에는 가중치가 있다. 모든 간선을 정확히 한 번씩 포함하는 사이클 집합을 만들 때, f(e1, e2) (두 간선 가중치의 최대값)의 합을 최소화하는 값을 구한다. N은 홀수임이 보장된다.
입력
- 첫째 줄: 노드 수 N (홀수)
- 이후 N*(N-1)/2개의 줄: 각 간선의 양 끝점 u, v와 가중치 w
출력
- 최소 비용의 합
예제
| 입력 | 출력 |
|---|---|
3 1 2 1 1 3 2 2 3 3 | 5 |
풀이
완전 그래프이고 N이 홀수임을 이용한 그리디 접근으로 해결한다. 각 노드에서 연결된 간선들을 오름차순 정렬한 뒤 짝수 인덱스를 건너뛰고 홀수 인덱스의 가중치만 합산한다.
- 완전 그래프이므로 각 노드의 차수는 N-1 (짝수)이다.
- 각 노드 i에 연결된 간선들의 가중치를
arr[i]리스트에 저장한다. - 각
arr[i]를 오름차순 정렬한다. - 각 노드에 대해 인덱스 1, 3, 5, ... (짝수 인덱스 건너뜀)의 가중치를 누적 합산한다.
- 최종 합이 답이다.
핵심 아이디어: N이 홀수인 완전 그래프에서 모든 간선을 한 번씩 포함하는 사이클 집합을 구성할 때, 각 노드별로 인접 간선을 정렬하고 짝수 번째(0-indexed) 간선을 쌍으로 묶으면 최솟값을 최소화할 수 있다. 각 노드는 짝수 개(N-1개)의 간선을 가지므로 쌍이 정확히 맞아떨어진다.
코드
package com.ssafy.an.day099;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;
public class Day79BOJ17966그래프와순회모든간선 { // 17966 Graph and Cycles
static final int INF = Integer.MAX_VALUE;
static int N, M;
static List<Integer>[] arr;
static long ans;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
N = Integer.parseInt(br.readLine());
ans = 0;
M = N * (N - 1) / 2; // 완전 그래프임을 의미함.
arr = new ArrayList[N + 1];
for (int i = 1; i < N + 1; i++)
arr[i] = new ArrayList<>();
for (int i = 0; i < M; i++) { // 간선 갯수 기준으로 노드별 list를 받는다.
st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
int w = Integer.parseInt(st.nextToken());
arr[u].add(w);
arr[v].add(w);
}
// 모든 간선을 지나는(노드 중복으로 들어와도 됨) 사이클 배열을 만든다.
// 홀수 개의 노드라도 정해져있기 때문에 무조건 한붓그리기 가능
// 완전 그래프임도 보장되기 때문에, 한 노드로부터 진행되는 간선은 짝수
// 각 노드별로 총 개수-1개 만큼 간선을 갖는다.
// 무방향이기 때문에 입력 받을 때, 시점, 끝점 배열에 가중치 추가
// f(e1, e2) 는 간선간의 가중치 최대값을 반환한다. << 다만,
for (int i = 1; i < N + 1; i++) {
Collections.sort(arr[i]); // bestSol
for (int j = 1; j < N; j += 2) { // 중복선택 회피
ans += arr[i].get(j);
} // N개(홀수)의 노드는 가 있으면, 각 노드는 N-1개 노드(짝수)를 갖는다.
}
print(arr);
System.out.println(ans);
br.close();
}
private static void print(List<Integer>[] a) {
StringBuilder tt = new StringBuilder();
for (int i = 1; i < arr.length; i++) {
for (int j = 0; j < arr[i].size(); j++) {
tt.append(arr[i].get(j)).append(" ");
}
tt.append("\n");
}
System.out.println(tt);
}
}복잡도
- 시간: O(N^2 log N) — N*(N-1)/2개의 간선 처리 + 각 노드별 정렬
- 공간: O(N^2) — 각 노드의 인접 가중치 리스트