04.01 학습&숙제

Dijkstra! 🟥🟧🟨🟩🟦🟪🟫⬜⬛🫢🔔😎😊🤔😭⭐

최단 경로 알고리즘

다익스트라(dijkstra) - 음의 가중치를 허용하지 않음
벨만-포드(Bellman-Ford) - 음의 가중치 허용
플로이드-워샬(Floyd-Warshall) - 모든 정점들에 대한 최단 경로

Dijkstra

시작 정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘
시작 정점에서의 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식이다.
탐욕 기법을 사용한 알고리즘으로 MST의 프림 알고리즘과 유사하다.

백준 4386번 별자리 만들기 (프림)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	static class Star implements Comparable<Star>{
		int to;
		double w;
		public Star(int to, double w) {
			super();
			this.to = to;
			this.w = w;
		}
		@Override
		public int compareTo(Star o) {
			return this.w - o.w < 0 ? -1 : 1;
		}
		
		
	}
	static int n; // 별의 갯수
	static double[] yArr,xArr; // 별의 x,y 좌표 
	static int[] visited; // 방문처리 
	static double res; // 정답 (최소비용)
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		n = Integer.parseInt(br.readLine());
		xArr = new double[n+1];
		yArr = new double[n+1];
		visited = new int[n+1];
		
		for(int i=1;i<=n;i++) {
			st = new StringTokenizer(br.readLine());
			xArr[i] = Double.parseDouble(st.nextToken());
			yArr[i] = Double.parseDouble(st.nextToken());
		}
		
		// 프림 시작 (1번째 Star 선택)
		PriorityQueue<Star> pq = new PriorityQueue<>();
		pq.add(new Star(1,0));
		res = 0D;
		while(!pq.isEmpty()) {
			Star cur = pq.poll();
			if(visited[cur.to] == 1) continue;
			visited[cur.to] = 1;
			res += cur.w;
			for(int i=1;i<=n;i++) {
				if(visited[i] == 1) continue;
				double dist = Math.sqrt(Math.pow(xArr[cur.to] - xArr[i], 2) + Math.pow(yArr[cur.to] - yArr[i], 2));
				pq.add(new Star(i,dist));
			}
		}
		
		System.out.printf("%.2f", res);
		
	}
}

숙제

정처기 실기 공부 시작! 1알고리즘!