728x90
https://www.acmicpc.net/problem/14950
메모리: 26,704 KB , 시간: 376 ms
사용 알고리즘: 그래프 이론, 최소 스패닝 트리
728x90
처음에 다익스트라로 풀었다가, 알고리즘 분류를 보고 크루스칼 알고리즘으로도 풀 수 있겠다고 알게 돼서 다시 크루스칼로 풀었다...
알고리즘 며칠 안 했다고 이전에는 당연히 크루스칼로 풀었을 문제를 다익스트라로 풀었네,,
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.PriorityQueue; import java.util.StringTokenizer; public class Main { static int[] parent; public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; st = new StringTokenizer(br.readLine()); int N = Integer.parseInt(st.nextToken()); int M = Integer.parseInt(st.nextToken()); int t = Integer.parseInt(st.nextToken()); // 크루스칼 알고리즘 PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[2] - o2[2]); int A, B, C; for (int i = 0; i < M; i++) { st = new StringTokenizer(br.readLine()); A = Integer.parseInt(st.nextToken()); B = Integer.parseInt(st.nextToken()); C = Integer.parseInt(st.nextToken()); pq.add(new int[] {A, B, C}); } parent = new int[N + 1]; for (int i = 1; i <= N; i++) { parent[i] = i; } int[] now; int result = 0; int count = 0; while(!pq.isEmpty()) { now = pq.poll(); if(union(now[0], now[1])) { // 아직 정복하지 않은 도시를 발견했을 경우 result += now[2] + (t * count++); // 비용 더하기 } } System.out.println(result); } private static int find(int a) { if(parent[a] == a) return a; return parent[a] = find(parent[a]); } private static boolean union(int a, int b) { a = find(a); b = find(b); // 이미 연결되어 있다면 false if(a == b) return false; // 아직 연결 전이라면 true; if(a < b) parent[b] = a; else parent[a] = b; return true; } }
728x90
'Problem Solving > BOJ' 카테고리의 다른 글
[백준, BOJ 2607] 비슷한 단어 (java) (0) | 2024.08.30 |
---|---|
[백준, BOJ 13414] 수강신청 (java) (0) | 2024.08.20 |
[백준, BOJ 9024] 두 수의 합 (java) (0) | 2024.07.26 |
[백준, BOJ 2058] 원자의 에너지 (java) (3) | 2024.07.25 |
[백준, BOJ 13424] 비밀 모임 (java) (0) | 2024.07.04 |