첫째 줄에 그래프의 정점의 수 V(1 ≤ V ≤ 50,000)와 간선의 수 E(1 ≤ E ≤ 200,000)가 들어온다. 둘째 줄부터 E+1번째 줄까지 한 간선으로 연결된 두 정점과 그 간선의 가중치가 주어진다. 가중치는 100,000보다 작거나 같은 자연수 또는 0이고, 답은 231-1을 넘지 않는다.
③ LCA ( DFS 활용 (깊이 구하기), Tree 만들기, 2^N 이용하기, DP적 활용 )
- LCA를 통해 교체 후보인 max, secondMax 확인
⑤ 긴 코드 작성시 버티는 근성
Java 코드 :
import java.io.*;
import java.util.*;
//1626 두 번째로 작은 스패닝 트리
public class Main {
static class edge implements Comparable<edge> {
int start, target, cost;
boolean isShortest;
public edge(int start, int target, int cost) {
this.start = start;
this.target = target;
this.cost = cost;
this.isShortest = false;
}
public edge(int target, int cost) {
this.target = target;
this.cost = cost;
}
@Override
public int compareTo(edge o) {
return this.cost - o.cost;
}
@Override
public String toString() {
return "edge [start=" + start + ", target=" + target + ", cost=" + cost + ", isShortest=" + isShortest
+ "]";
}
}
// MST 재료들
static int V, E;
static ArrayList<edge> edgeList;
static int[] parent;
// LCA 재료들
static ArrayList[] adjList;
static int[] depth;
static int[][] lcaParent;
static int[][] maxDist;
static int[][] secMaxDist;
static int K;
static StringBuilder sb;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
V = Integer.parseInt(st.nextToken());
E = Integer.parseInt(st.nextToken());
edgeList = new ArrayList<edge>();
int a, b, w;
for (int i = 0; i < E; i++) {
st = new StringTokenizer(br.readLine());
a = Integer.parseInt(st.nextToken());
b = Integer.parseInt(st.nextToken());
w = Integer.parseInt(st.nextToken());
edgeList.add(new edge(a, b, w));
}
// 1. MST - 크루스칼
parent = new int[V + 1];
for (int i = 1; i <= V; i++) {
parent[i] = i;
}
adjList = new ArrayList[V + 1];
for (int i = 1; i <= V; i++) {
adjList[i] = new ArrayList<edge>();
}
int cnt = 0; // 탈출조건
int cost = 0; // MST 비용
Collections.sort(edgeList);
for (int i = 0; i < E; i++) {
// ** 탈출조건 - MST 완성시 탈출
if (cnt == V - 1)
break;
edge now = edgeList.get(i);
int pa = find(now.start);
int pb = find(now.target);
// 1) 이미 같은 그룹이면 continue
if (pa == pb) continue;
// 2) 다른 그룹이므로 union
union(now.start, now.target);
cost += now.cost;
now.isShortest = true; // MST 간선으로 기록
cnt++;
// 최소신장트리를 가지고 LCA를 돌려야하므로 새로운 인접리스트에 넣기
adjList[now.start].add(new edge(now.target, now.cost));
adjList[now.target].add(new edge(now.start, now.cost));
}
// 1-1. MST 없는 경우
if (cnt != V - 1 || E <= V - 1) {
System.out.println(-1);
br.close();
return;
}
// 2. LCA 준비
// 2-1. LCA 관련 변수 초기화
// 2^K >= N인 첫번째 K 찾기, 문제조건 : N >= 2, K를 -1부터 시작해야 아래 값이 나옴
// N이 17이면 2^4 번째 조상까지 기록 필요 17 = 2^4 + 2^0
// N이 16이면 2^4 번째 조상까지 기록 필요 16 = 2^4
// N이 15이면 2^3 번째 조상까지 기록 필요 15 = 2^3 + 2^2 + 2^1 + 2^0
K = -1;
for (int i = 1; i <= V; i *= 2) {
K++;
}
depth = new int[V + 1];
lcaParent = new int[K + 1][V + 1];
maxDist = new int[K + 1][V + 1];
secMaxDist = new int[K + 1][V + 1];
// 2-2. DEPTH 확인
dfs(1, 1);
// 2-3. 2^N 까지 parent 채우기
fillParent();
// 3. 모든 edge를 보면서 교체할지 검토
// 불가능하다고 가정하고 시작
// ans는 빼야하는 값 ( 음수 )
long ans = Long.MAX_VALUE;
int max = 0;
// 모든 edge를 보면서 교체할지 검토
for (int i = 0; i < E; i++) {
edge now = edgeList.get(i);
// MST에 해당하면 continue (교체 안됨)
if (now.isShortest) {
continue;
}
// lca를 보면서 가능한 교체 값(max) 확인
max = lca(now.start, now.target, now.cost);
if (max == -1 ) continue;
ans = Math.min(ans, now.cost - max);
}
// 4. 정답출력
if (ans == Long.MAX_VALUE) {
System.out.println(-1);
} else {
System.out.println(cost + ans);
}
br.close();
}
// MST를 위한 union find
static int find(int id) {
if (parent[id] == id)
return id;
return parent[id] = find(parent[id]);
}
// MST를 위한 union find
static void union(int a, int b) {
int pa = find(a);
int pb = find(b);
parent[pb] = pa;
}
// DEPTH 확인, 첫번째 조상확인 - MST 해당되는 애들만 DFS
static void dfs(int id, int cnt) {
// 1. depth를 기록
depth[id] = cnt;
// 2. 자식들의 depth를 기록
int len = adjList[id].size();
for (int i = 0; i < len; i++) {
edge next = (edge) adjList[id].get(i);
// 아직 깊이를 모르면 → 미방문 노드
if (depth[next.target] == 0) {
dfs(next.target, cnt + 1);
lcaParent[0][next.target] = id; // 첫번째 부모를 기록
// maxDist 초기값 세팅 ( 부모-자식 사이에 cost로 초기 값, second는 아직 없음 )
maxDist[0][next.target] = next.cost;
secMaxDist[0][next.target] = -1;
}
}
return;
}
// 부모 채우기
static void fillParent() {
// 첫번째 max, 두번째 max를 모두 확인
int max, secMax;
// 부모의 max, 두번째 max
int paMax, paSecMax;
for (int i = 1; i <= K; i++) {
for (int j = 1; j <= V; j++) {
int pid = lcaParent[i-1][j];
// MST 해당되는 애들만 LCA를 타자
// MST 해당되는 애들을 dfs 때 pid 를 기록해놓음
if (pid != 0 && lcaParent[i-1][pid] != 0) {
// j가 조상으로 갈때
max = maxDist[i-1][j];
secMax = secMaxDist[i-1][j];
// pid가 조상으로 갈때
paMax = maxDist[i-1][pid];
paSecMax = secMaxDist[i-1][pid];
// 1) max가 더 크면 max 로 갱신
if (max > paMax) {
maxDist[i][j] = max;
// 2위 결정전
secMaxDist[i][j] = Math.max(paMax, secMax);
}
// 2) paMax가 더 크면 paMax로 갱신
else if (max < paMax) {
maxDist[i][j] = paMax;
// 2위 결정전
secMaxDist[i][j] = Math.max(max, paSecMax);
}
// 3) 둘이 같으면 2위 결정전에서 2위끼리 대결
else {
maxDist[i][j] = max;
secMaxDist[i][j] = Math.max(secMax, paSecMax);
}
lcaParent[i][j] = lcaParent[i-1][pid];
}
}
}
}
// 최소공통조상
static int lca(int a, int b, int cost) {
// 1. depth[a] >= depth[b] 이도록 조정하기
if (depth[a] < depth[b]) {
int tmp = a;
a = b;
b = tmp;
}
// 불가능하다고 가정하고 시작
int ret = -1;
// 2. 더 깊은 a를 2^K승 점프하여 depth를 맞추기
for (int i = K; i >= 0; i--) {
if (Math.pow(2, i) <= depth[a] - depth[b]) {
// 첫번째로 큰값을, 현재의 cost로 대체가 가능하다면
if (maxDist[i][a] != cost) {
ret = Math.max(ret, maxDist[i][a]);
}
// 첫번째로 큰 값은 안되더라도, 두번째로 큰 값이 된다면
else if (secMaxDist[i][a] != -1) {
ret = Math.max(ret, secMaxDist[i][a]);
}
// depth 전진
a = lcaParent[i][a];
}
}
// 3. depth를 맞췄는데 같다면 종료
if (a == b) return ret;
// 4. a-b는 같은 depth이므로 2^K승 점프하며 공통부모 바로 아래까지 올리기
for (int i = K; i >= 0; i--) {
if (lcaParent[i][a] != lcaParent[i][b]) {
// a ~ 최소공통조상까지 max가 있는지 확인
if (maxDist[i][a] != cost) {
ret = Math.max(ret, maxDist[i][a]);
}
else if (secMaxDist[i][a] != -1) {
ret = Math.max(ret, secMaxDist[i][a]);
}
// b ~ 최소공통조상까지 max가 있는지 확인
if (maxDist[i][b] != cost) {
ret = Math.max(ret, maxDist[i][b]);
} else if (secMaxDist[i][b] != -1) {
ret = Math.max(ret, secMaxDist[i][b]);
}
a = lcaParent[i][a];
b = lcaParent[i][b];
}
}
// a ~ 바로 윗 조상 사이에 max인지 확인
if (maxDist[0][a] != cost) {
ret = Math.max(ret, maxDist[0][a]);
} else if (secMaxDist[0][a] != -1) {
ret = Math.max(ret, secMaxDist[0][a]);
}
// b ~ 바로 윗 조상 사이에 max인지 확인
if (maxDist[0][b] != cost) {
ret = Math.max(ret, maxDist[0][b]);
} else if (secMaxDist[0][b] != -1) {
ret = Math.max(ret, secMaxDist[0][b]);
}
return ret;
}
}
