풀이 방법
MST를 이용해서 모든 마을을 연결할 수 있는 최소 비용을 구해주었다.
그 경로 중 마을과 마을을 이동할 때 최악의 비용이 얼마인지 구해주기 위해 MST를 저장해주었다.
최악의 비용을 구하기 위해서는 임의의 한곳에서 dfs로 가장 먼 노드를 찾아주고 그 노드를 시작으로 dfs를 하면 나오게 된다.
내 코드
package com.company;
import java.io.*;
import java.util.*;
public class Main {
static int K, N, max, start;
static int[][] arr;
static int[][] arr2;
static boolean[] visited;
static Queue<Node> pq = new PriorityQueue<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
arr = new int[N][N];
arr2 = new int[N][N];
visited = new boolean[N];
for (int i = 0; i < K; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
arr[a][b] = c;
arr[b][a] = c;
}
visited[0] = true;
for (int i = 0; i < N; i++) {
if (arr[0][i] != 0)
pq.offer(new Node(0, i, arr[0][i]));
}
int count = 1;
int answer = 0;
while (!pq.isEmpty()) {
if (count == N) {
break;
}
Node node = pq.poll();
if (visited[node.a] && visited[node.b])
continue;
answer += node.c;
arr2[node.a][node.b] = node.c;
arr2[node.b][node.a] = node.c;
if (visited[node.a] && !visited[node.b]) {
count++;
visited[node.b] = true;
for (int i = 0; i < N; i++) {
if (arr[node.b][i] != 0 && !visited[i])
pq.offer(new Node(node.b, i, arr[node.b][i]));
}
} else if (!visited[node.a] && visited[node.b]) {
count++;
visited[node.a] = true;
for (int i = 0; i < N; i++) {
if (arr[node.a][i] != 0 && !visited[i])
pq.offer(new Node(node.a, i, arr[node.a][i]));
}
}
}
max = 0;
start = 0;
Arrays.fill(visited, false);
visited[start] = true;
dfs(start, 0);
Arrays.fill(visited, false);
visited[start] = true;
dfs(start, 0);
System.out.println(answer);
System.out.println(max);
}
static void dfs(int index, int cost) {
if (max < cost) {
max = cost;
start = index;
}
max = Math.max(cost, max);
for (int i = 0; i < N; i++) {
if (!visited[i] && arr2[index][i] != 0) {
visited[i] = true;
dfs(i, arr2[index][i] + cost);
visited[i] = false;
}
}
}
}
class Node implements Comparable<Node> {
int a, b, c;
public Node(int a, int b, int c) {
this.a = a;
this.b = b;
this.c = c;
}
@Override
public int compareTo(Node o) {
return this.c - o.c;
}
}
'코딩테스트 > [백준] 코딩테스트 연습' 카테고리의 다른 글
줄세우기 - 2631번 (0) | 2021.12.28 |
---|---|
그대, 그머가 되어 - 14496번 (0) | 2021.12.27 |
플로이드 - 11404번 (0) | 2021.12.24 |
쉬운 계단 수 - 10844번 (0) | 2021.12.03 |
최소 힙 - 1927번 (0) | 2021.12.03 |