반응형
https://www.acmicpc.net/problem/13418
13418번: 학교 탐방하기
입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 건물의 개수 N(1 ≤ N ≤ 1,000)과 도로의 개수 M(1 ≤ M ≤ N(N-1)/2) 이 주어진다. 입력의 두 번
www.acmicpc.net
최소 신장 트리 (MST)를 알아야 풀 수 있는 문제다.
문제는 (최대 신장 트리 - 최소 신장 트리)의 값을 요구한다.
제곱을 해줘야 하긴 하지만 사소하기 때문에
MST를 적용하면 풀 수 있는 문제다.
크루스칼, 프림 모두 적용 가능하며 크루스칼을 이용해서 해결했다.
우선순위 큐에서 최대 신장 트리, 최소 신장 트리로 정렬할 수 있도록
두 가지 방식으로 정렬하는 큐를 만들어서
간선들을 넣어준후 크루스칼 알고리즘을 적용했다.
이 문제의 최대 주의할 점은
오르막길이 1이라고 착각할 수 있다.
오르막길은 0이다.
예제는 오르막길이 1이라고 판단해도 정답이 되기 때문에 주의해야 한다.
코드구현
|
import java.io.*;
import java.util.*;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static Queue<Edge> q1;
static Queue<Edge> q2;
static int[] arr;
public static void main(String[] args) throws IOException {
StringTokenizer st = new StringTokenizer(br.readLine());
int E = Integer.parseInt(st.nextToken());
int V = Integer.parseInt(st.nextToken()) + 1;
arr = new int[E+1];
for(int i = 0; i<arr.length; i++){
arr[i] = i;
}
q1 = new PriorityQueue<>((o1, o2) -> o1.v - o2.v);
q2 = new PriorityQueue<>((o1, o2) -> o2.v - o1.v);
while(V-- > 0){
st = new StringTokenizer(br.readLine());
int w1 = Integer.parseInt(st.nextToken());
int w2 = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
Edge e = new Edge(w1,w2,v);
q1.offer(e);
q2.offer(e);
}
//
int ms = (int) Math.pow(mst(0,q1),2); // max
//
for(int i = 0; i<arr.length; i++)
arr[i] = i;
int Ms = (int) Math.pow(mst(0,q2), 2); // min
System.out.println(ms-Ms);
}
public static int find(int e){ // 대표원소 갖고오기.
if(arr[e] == e)
return e;
else
return arr[e] = find(arr[e]);
}
public static void union(int w1, int w2){ // 대표원소 바꿔주기.
w1 = find(w1);
w2 = find(w2); // 대표원소를 찾아왔음
if(w1 < w2){
arr[w2] = w1;
}else
arr[w1] = w2;
}
public static int mst(int start, Queue<Edge> q){
int sum = 0;
while(!q.isEmpty()){
Edge e = q.poll();
int w11 = e.w1;
int w21 = e.w2;
int v1 = e.v;
if(find(w11) != find(w21)){
union(w11, w21);
// 처리부분.
if(v1 == 0)
sum += 1;
}
}
return sum;
}
}
class Edge {
int w1;
int w2;
int v;
Edge(int w1, int w2, int v){
this.w1 = w1;
this.w2 = w2;
this.v = v;
}
}
|
cs |
반응형
'문제풀이 > 코딩 문제 풀이' 카테고리의 다른 글
| [백준] 14501번 퇴사 (JAVA) (0) | 2022.04.21 |
|---|---|
| [백준] 1253번 좋다 (JAVA) (0) | 2022.04.19 |
| [백준] 2252번 줄세우기 (JAVA) (0) | 2022.04.15 |
| [백준] 1992번 쿼드트리 (JAVA) (0) | 2022.03.20 |
| [백준] 2448번 별 찍기 - 11 (JAVA) (0) | 2022.03.19 |