[BOJ1368] 물대기 (프림 알고리즘, 최소 신장 트리, 그리디)알고리즘/탐욕(그리디)2023. 9. 6. 21:21
Table of Contents
반응형
문제 링크
https://www.acmicpc.net/problem/1368
문제 풀이
문제를 접근할 때 우물을 무조건 하나 파야 한다고 생각해서
제일 적은 비용이 드는 우물을 기준으로 구했으나 '틀렸습니다' 만 나왔다
기술 블로그를 찾아본 결과, 우물을 하나 파는 행위를 간선(Edge) 정보로 추가해서 풀이해야 했다.
- 임의 노드 0번에 {i번 논, 논을 파는 비용} 으로 정의해서 컬렉션에 담는다
- 그리고 0번 노드부터 시작하여 결과값을 구하니 통과가 되었다
0 -> 4 -- 비용 3 (최초 4번 논을 판다)
4 -> 1 -- 비용 2
1 -> 2 -- 비용 2
1 -> 3 -- 비용 2
총 비용: 9
프림 알고리즘을 사용했고, 비용 기준으로 오름차순 정렬
시간 복잡도 : O(ElogV)
제출 코드
import java.util.*;
import java.io.*;
public class Main {
static int N;
static List<Edge>[] adj;
static class Edge implements Comparable<Edge> {
int idx;
int cost;
public Edge(int idx, int cost) {
this.idx = idx;
this.cost = cost;
}
@Override
public int compareTo(Edge edge) {
return cost - edge.cost;
}
}
static void input() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
// 논을 파는 비용
int[] w = new int[N + 1];
for(int i = 1; i <= N; i++) {
w[i] = Integer.parseInt(br.readLine());
}
adj = new ArrayList[N + 1]; // 0번 노드까지 초기화
for(int i = 0; i <= N; i++) adj[i] = new ArrayList<>();
for(int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine());
for(int j = 1; j <= N; j++) {
int cost = Integer.parseInt(st.nextToken());
if(i != j) adj[i].add(new Edge(j, cost));
else adj[0].add(new Edge(i, w[i])); // 논을 파는 행위를 간선 정보로 저장
}
}
}
static int prime(int start) {
Queue<Edge> que = new PriorityQueue<>();
que.add(new Edge(start, 0));
boolean[] visit = new boolean[N + 1];
int result = 0;
while(!que.isEmpty()) {
Edge cur = que.poll();
if(visit[cur.idx]) continue;
visit[cur.idx] = true;
result += cur.cost;
for(Edge next : adj[cur.idx]) {
if(visit[next.idx]) continue;
que.add(next);
}
}
return result;
}
static void pro() {
System.out.println(prime(0));
}
public static void main(String[] args) throws Exception {
input();
pro();
}
}
반응형
'알고리즘 > 탐욕(그리디)' 카테고리의 다른 글
[BOJ2887] 행성 터널(최소신장트리,MST, 크루스칼 알고리즘) (0) | 2023.09.22 |
---|---|
[BOJ20010] 악덕 영주 혜유 (크루스칼, 프림, MST, 최소신장트리, 트리의 지름) (0) | 2023.09.07 |
[BOJ4386] 별자리 만들기 (프림 알고리즘, 최소신장트리, MST) (0) | 2023.09.06 |
[BOJ1414] 불우이웃돕기 (프림, 최소 신장트리, 그리디) (0) | 2023.09.06 |
[BOJ6497] 전력난 (크루스칼, 프림, 최소 신장트리, MST) (0) | 2023.09.06 |
@leejinwoo1126 :: 천천히 하나씩
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!