[백준] 1753번 최단경로 자바

문제 (골드5, 다익스트라 알고리즘)

 

1753번: 최단경로

 

 

문제풀이

 

처음에 다익스트라 알고리즘인 줄 모르고 DFS로 풀었다.

정점과 가중치 값을 ' , '로 연결하여 ArrayList에 String값을 담아서 도착 정점까지의 가중치합을 합하여 weight배열에 담아줬었다.

도착정점까지 가는 모든 가중치합을 비교하며 weight배열을 갱신하고 마지막에 출력해줬다.

 

이렇게...

public class Main {

	static int[] weight;
	static ArrayList<String>[] list;
	static boolean check;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int V = sc.nextInt();
		int E = sc.nextInt();
		int startV = sc.nextInt();
		
		weight = new int[V+1];
		list = new ArrayList[V+1];
		for(int i = 1; i < V+1; i++)
			list[i] = new ArrayList<String>();
		
		for(int i = 0; i < E; i++) {
			int u = sc.nextInt();
			int v = sc.nextInt();
			int w = sc.nextInt();
			String temp = String.valueOf(v) + "," + String.valueOf(w);
			list[u].add(temp);
		}
		
		for(int i = 1; i <= V; i++) {
			if(i != startV) {
				check = false;
				DFS(startV, i, 0);
				if(check == false)
					weight[i] = -1;
			}
		}
		
		for(int i = 1; i <= V; i++) {
			if(weight[i] == -1)
				System.out.println("INF");
			else
				System.out.println(weight[i]);
		}
		
		sc.close();
		return;
	}
	
	static void DFS(int start, int destination, int total) {
		if(start == destination) {
			if(weight[destination] == 0 || total < weight[destination])
				weight[destination] = total;
			check = true;
			return;
		}
		
		for(String str : list[start]) {
			String[] s = str.split(",");
			int v = Integer.parseInt(s[0]);
			int w = Integer.parseInt(s[1]);
			DFS(v, destination, total+w);
		}
	}
}

 

 

테스트케이스는 맞았지만 제출해보면

 

...^^,,

 

그래서 인터넷에 찾아보니 다익스트라 알고리즘이었고, 단순히 배열로 구현할 수는 있지만 배열 + 우선순위 큐를 이용하여 구현해야 시간 효율성이 훨씬 뛰어났다.

 

다익스트라 알고리즘이란 하나의 정점에서 다른 점들로 가는 최단경로(거리)를 구할 때 사용하는 알고리즘이다. (단, 음의 가중치가 없어야 함)

1. 정점의 최단거리 값을 담을 배열을 하나 생성

2. 자기자신은 0으로, 그 외에는 INF값으로 초기화

3. 시작 정점(자신)을 방문 했을 때, 연결가능한 다른 정점 값들 갱신

4. 시작정점에서 뻗어가는 가장 작은 가중치를 가진 정점 방문

5. 방문정점의 현재 배열값과 현재정점 배열값+방문정점과 연결된 가중치값 중 작은 값으로 업데이트 

 

참고: https://jellyinghead.tistory.com/78

 

 

소스코드

 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

public class b_1753 {
	
	static ArrayList<Node>[] list;
	static int dist[];
	static boolean[] visited;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int V = sc.nextInt();
		int E = sc.nextInt();
		int startV = sc.nextInt();
		
		visited = new boolean[V+1];
		list = new ArrayList[V+1];
		dist = new int[V+1];
		
		Arrays.fill(dist, -1); 	//dist배열 -1로 채우기
		dist[startV] = 0;		// 시작 정점
		
		for(int i = 1; i <= V; i++)
			list[i] = new ArrayList<>();
		
		for(int i = 0; i < E; i++) {
			int u = sc.nextInt();
			int v = sc.nextInt();
			int w = sc.nextInt();
			list[u].add(new Node(v, w));
		}
		
		Dijkstra(startV);
		for(int i = 1; i <= V; i++) {
			if(dist[i] == -1)
				System.out.println("INF");
			else
				System.out.println(dist[i]);
		}
		
	}
	
	static void Dijkstra(int start) {
		PriorityQueue<Node> q = new PriorityQueue<>();
		
		q.add(new Node(start, 0)); //값 추가
		
		while(!q.isEmpty()) {
			Node now = q.poll();	// 큐의 첫번째 값 반환후 제거
			if(visited[now.node])
				continue;
			
			visited[now.node] = true;
			for(Node next : list[now.node]) {
				if(dist[next.node]==-1 || dist[next.node] > dist[now.node]+next.weight) {
					dist[next.node] = dist[now.node] + next.weight;
					q.add(new Node(next.node, dist[next.node]));
				}
			}
		}
	}
	
	private static class Node implements Comparable<Node>{
		int node, weight;
		
		Node(int n, int w){
			this.node = n;
			this.weight = w;
		}
		
		public int compareTo(Node n) {
			return weight - n.weight;
		}
	}

}