본문 바로가기

알고리즘 Algorithm/BOJ 백준 (초급~중급)

[BOJ 백준] 두 번째로 작은 스패닝 트리(1626) Java

반응형

링크 : https://www.acmicpc.net/problem/1626

 

문제 설명 : 

더보기

방향성이 없는 그래프 G가 주어진다. 문제는 G의 최소 스패닝 트리보다는 크면서 가장 작은 스패닝 트리인 'The second minimum spanning tree'를 구하는 것이다.

MST와 second MST의 모습

 

입력 : 

더보기

첫째 줄에 그래프의 정점의 수 V(1 ≤ V ≤ 50,000)와 간선의 수 E(1 ≤ E ≤ 200,000)가 들어온다. 둘째 줄부터 E+1번째 줄까지 한 간선으로 연결된 두 정점과 그 간선의 가중치가 주어진다. 가중치는 100,000보다 작거나 같은 자연수 또는 0이고, 답은 231-1을 넘지 않는다.

정점 번호는 1보다 크거나 같고, V보다 작거나 같은 자연수이다.

 

출력 : 

더보기

두 번째로 작은 스패닝 트리의 값을 출력한다. 만약 스패닝 트리나 두 번째로 작은 스패닝 트리가 존재하지 않는다면 -1을 출력한다.

 

예제 입력 : 

더보기

7 12
1 2 8
1 3 5
2 3 10
2 4 2
2 5 18
3 4 3
3 6 16
4 5 12
4 6 30
4 7 14
5 7 4
6 7 26

 

예제 출력 : 

 

접근법 : 

1) 어떻게 풀 것인가?

추가 예정

 

자세한 내용은 코드 참고.

 

2) 시간복잡도

O (N log N) 

(Java 기준 -  1,180ms)

 

3) 공간복잡도

큰 변수 없어 고려하지 않음.

 

4) 풀면서 놓쳤던점

매우 많아서 정리 필요

 

5) 이 문제를 통해 얻어갈 것

① 유니온파인드

② MST

③ LCA ( DFS 활용 (깊이 구하기), Tree 만들기, 2^N 이용하기, DP적 활용 )

④ LCA를 통한 싸이클 활용

⑤ 긴 코드 작성시 버티는 근성

 

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
					+ "]";
		}

	}

	static int V, E;
	static int[][] dp; // dp[i][j] = 1번 경찰차가 i번 사건을 처리했고, 2번 경찰차가 j번 사건을 처리했을때 최소비용
	static ArrayList<edge> edgeList;
	static int[] parent;

	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));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		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 비용

		edgeList.sort(null);

		for (int i = 0; i < E; i++) {

			if (cnt == V - 1)
				break; // MST 완성시 탈출

			edge now = edgeList.get(i);

			int pa = find(now.start);
			int pb = find(now.target);

			if (pa == pb)
				continue; // 이미 같은 팀
			union(now.start, now.target);
			cost += now.cost;
			now.isShortest = true; // MST 간선 기록

			// lca 준비물
			adjList[now.start].add(new edge(now.target, now.cost));
			adjList[now.target].add(new edge(now.start, now.cost));
			cnt++;
		}

		// 1-1. MST 없는 경우
		if (cnt != V - 1 || E <= V - 1) {
			bw.write("-1");
			
			bw.flush();
			bw.close();
			br.close();
			return;
		}

		// 2. LCA 구현
		// 2-1. LCA 관련 변수 초기화
		K = 0;
		for (int i = 1; i <= V; i *= 2) {
			K++;
		}

		depth = new int[V + 1];
		lcaParent = new int[K][V + 1];
		maxDist = new int[K][V + 1];
		secMaxDist = new int[K][V + 1];

		// 2-2. DEPTH 확인
		dfs(1, 1);

		// 3. 2^N 까지 parent 채우기
		fillParent();

		// bw.write(sb.toString());

		long ans = Long.MAX_VALUE;
		int max = 0;
		for (int i = 0; i < E; i++) {
			edge now = edgeList.get(i);
			if (now.isShortest) continue;
			max = check(now.start, now.target, now.cost);
			if (max == -1 || max ==  now.cost) continue;
			ans = Math.min(ans, now.cost-max);
		}

		if (ans == Long.MAX_VALUE) {
			bw.write(String.valueOf(-1));
		}
		else {
			bw.write(String.valueOf(ans+cost));
		}

		bw.flush();
		bw.close();
		br.close();
	}

	static int find(int id) {
		if (parent[id] == id)
			return id;
		return parent[id] = find(parent[id]);
	}

	static void union(int a, int b) {
		int pa = find(a);
		int pb = find(b);
		parent[pb] = pa;
	}

	// DEPTH 확인 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[0][next.target] = next.cost;
				secMaxDist[0][next.target] = -1;
			}
		}
		return;
	}

	// 부모 채우기
	static void fillParent() {
		int max, secMax;
		int paMax, paSecMax;
		for (int i = 0; i < K; i++) {
			for (int j = 1; j <= V; j++) {
				int pid = lcaParent[i][j];
				if (pid!=0 && lcaParent[i][pid]  !=0) {
					
					// j가 조상으로 갈때
					max = maxDist[i][j];
					secMax = secMaxDist[i][j];
					
					// pid가 조상으로 갈때
					paMax = maxDist[i][pid];
					paSecMax = secMaxDist[i][pid];
					
					if (max > paMax) {
						maxDist[i+1][j] = max;
						secMaxDist[i+1][j] = Math.max(paMax, secMax);
					}
					
					else if (max < paMax) {
						maxDist[i+1][j] = paMax;
						secMaxDist[i+1][j] = Math.max(max,  paSecMax); 
					}
					
					else {
						maxDist[i+1][j] = max;
						secMaxDist[i+1][j] = Math.max(secMax, paSecMax);
					}
					lcaParent[i+1][j] = lcaParent[i][pid];
				}
			}
		}
	}

	// 최소공통조상
	static int check(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 - 1; i >= 0; i--) {
			if (Math.pow(2, i) <= depth[a] - depth[b]) {
				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]);
				}
				a = lcaParent[i][a];
			}
		}

		// 3. depth를 맞췄는데 같다면 종료
		if (a == b) return ret;

		// 4. a-b는 같은 depth이므로 2^K승 점프하며 공통부모 바로 아래까지 올리기
		for (int i = K - 1; i >= 0; i--) {
			if (lcaParent[i][a] != lcaParent[i][b]) {

				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]);
				}

				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];
			}
		}

		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]);
		}

		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]);
		}

		// 원래였으면 lcaParent도 한 번 갱신
		
		return ret;
	}

}
반응형