문제 풀이 날짜: 2023.08.24
포스트 작성일: 2023.08.26
* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.
문제 출처
SWEA 1251번: 하나로 (D4)
키워드
프림 알고리즘
풀이 접근법
- 기초적인 프림 알고리즘을 활용하여 풀이한다. 입력 형식에 맞게 인접 리스트로 그래프를 구현한다.
- 문제의 입력으로 각 정점 사이의 거리만이 주어지는데, 프림 알고리즘에서는 정점 기반으로 다음 정점으로 가는 가장 가중치가 작은 간선을 선택해야 한다. 따라서 한 점에서 다른 모든 점으로 향하는 간선을 일괄 생성해준다.
- 정점 간의 거리(dist)와 도착 정점 정보(u)를 저장하는 Vertex 클래스를 생성하여 인접리스트에 넣어주었다.
- 우선순위 큐에 저장된 정점들을 순회하며 거리가 최소인 간선부터 뽑는다. 방문한 적 있는 정점이면 다음 정점을 뽑고, 방문한 적 없는 정점이라면 해당 정점과 연결된 간선들을 큐에 넣어준다.
- 우선순위 큐가 빌 때까지 위 과정을 반복한다.
코드
import java.io.*;
import java.util.*;
public class Solution {
static class Vertex implements Comparable<Vertex> {
int num; // 정점 번호
long weight; // 트리 정점과 연결했을 때 간선 비용
public Vertex(int num, long weight) {
this.num = num;
this.weight = weight;
}
@Override
public int compareTo(Vertex o) {
return Long.compare(this.weight, o.weight);
}
}
private static List<Vertex>[] adjList; // 인접 리스트
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
for (int test_case = 1; test_case <= T; test_case++) {
int N = Integer.parseInt(br.readLine());
adjList = new LinkedList[N];
for (int i = 0; i < N; i++) {
adjList[i] = new LinkedList<>();
}
boolean[] visited = new boolean[N];
PriorityQueue<Vertex> pq = new PriorityQueue<>();
int[] px = new int[N];
int[] py = new int[N];
StringTokenizer st;
st = new StringTokenizer(br.readLine(), " ");
for (int i = 0; i < N; i++) {
px[i] = Integer.parseInt(st.nextToken());
}
st = new StringTokenizer(br.readLine(), " ");
for (int i = 0; i < N; i++) {
py[i] = Integer.parseInt(st.nextToken());
}
double E = Double.parseDouble(br.readLine());
for(int v = 0; v < N; v++) {
for(int u = 0; u < N; u++) {
if(v == u) continue;
long distX = Math.abs(px[v] - px[u]);
long distY = Math.abs(py[v] - py[u]);
long dist = distX * distX + distY * distY;
adjList[v].add(new Vertex(u, dist));
}
}
pq.offer(new Vertex(0, 0));
sb.append("#").append(test_case).append(" ");
int count = 0;
long result = 0; // 최소 신장 트리 비용
long minWeight = 0;
int minVertex = 0;
while(!pq.isEmpty()) {
Vertex curr = pq.poll();
minWeight = curr.weight;
minVertex = curr.num;
if (visited[minVertex]) {
continue;
}
visited[minVertex] = true;
result += minWeight;
if (++count == N) {
break;
}
int size = adjList[minVertex].size();
for (int i = 0; i < size; i++) {
Vertex next = adjList[minVertex].get(i);
if (!visited[next.num]) { //연결된 다음 노드와 연결되었는지 확인
pq.offer(next);
}
}
}
sb.append(Math.round(result * E)).append("\n");
}
System.out.println(sb);
}
}
git 링크
(git 링크 첨부)
'Study > Problem Solving' 카테고리의 다른 글
| [백준 / Java] 1010번: 다리 놓기 (실버5) (0) | 2023.08.30 |
|---|---|
| [백준 / Java] 15961번: 회전초밥 (골드4) (0) | 2023.08.26 |
| [백준 / Java] 17471번: 게리맨더링 (골드4) (0) | 2023.08.26 |
| [SWEA / Java] 3289번: 서로소 집합 (D4) (0) | 2023.08.26 |
| [백준 / Java] 2252번: 줄 세우기 (골드3) (0) | 2023.08.23 |
