풀이 방법
최소 비용 신장 트리를 만드는 문제이다.
그리디 방법을 사용해서 트리를 만들었는데 각 경로를 나타내는 Node 클래스를 만들어서 priorityQueue를 이용했다.
내 코드
package com.company;
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
int N = Integer.parseInt(br.readLine());
int M = Integer.parseInt(br.readLine());
ArrayList<ArrayList<Node>> list = new ArrayList<>();
boolean[] visited = new boolean[N + 1];
for (int i = 0; i <= N; i++) {
list.add(new ArrayList<>());
}
int start = 100000;
int cost = 100000;
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
if (cost > c) {
start = a;
cost = c;
}
list.get(a).add(new Node(a, b, c));
list.get(b).add(new Node(b, a, c));
}
for (int i = 0; i <= N; i++) {
Collections.sort(list.get(i));
}
int min = 0;
PriorityQueue<Node> q = new PriorityQueue<>();
q.add(new Node(0, start, 0));
while (!q.isEmpty()) {
Node n = q.poll();
if (visited[n.b])
continue;
min += n.c;
visited[n.b] = true;
for (int i = 0; i < list.get(n.b).size(); i++) {
if (!visited[list.get(n.b).get(i).b]) {
q.add(list.get(n.b).get(i));
}
}
}
System.out.println(min);
}
}
class Node implements Comparable<Node> {
int a;
int b;
int c;
Node(int a, int b, int c) {
this.a = a;
this.b = b;
this.c = c;
}
@Override
public int compareTo(Node other) {
if (this.c < other.c)
return -1;
return 1;
}
}
'코딩테스트 > [백준] 코딩테스트 연습' 카테고리의 다른 글
점수따먹기 - 1749번 (0) | 2021.10.25 |
---|---|
색종이와 가위 - 20444번 (0) | 2021.10.25 |
오리 - 12933번 (0) | 2021.10.22 |
운동 - 1956번 (0) | 2021.10.21 |
이동하기 - 11048번 (0) | 2021.10.19 |