[SWEA / Java] 1251번: 하나로 (D4)

문제 풀이 날짜: 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 링크 첨부)