[BOJ] 1753: 최단경로(JAVA)

https://www.acmicpc.net/problem/1753

1753번: 최단경로

 

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

입력

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

출력

첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.

예제 입력 1 

5 6

1

5 1 1

1 2 2

1 3 3

2 3 4

2 4 5

3 4 6

예제 출력 1 

0

2

3

7

INF

---

[문제 풀이]

다익스트라(Dijkstra) 알고리즘을 적용하여 해결하는 문제이다. 플로이드 와샬 알고리즘을 이용하여 해결해도 답은 나오지만 메모리초과가 난다.

다익스트라 알고리즘은 한 정점에서 모든 정점으로 가는 최단 경로를 구하고 싶을 때 사용한다.

 

위의 입력을 그래프로 표현하면 다음과 같다.

정수 배열 dist는 최단 경로를 저장할 배열이다.

1. 출발 정점 1을 제외한 나머지 값들을 INF로 초기화 한다. INF값은 Integer.MAX_VALUE라고 한다.

1	2	3	4	5
0	INF	INF	INF	INF

2. 1번 정점에서 갈 수있는 모든 정점을 탐색하고 최솟값으로 dist를 업데이트한다. 업데이트 한 값들 중 최솟값은 2번 정점이므로 다음 탐색할 정점은 2번 정점이 된다.

1	2	3	4	5
0	2(=dist[1]+(1->2로 가는 cost) = 0+2)	3(=dist[1]+(1->3로 가는 cost) = 0+3)	INF	INF

3. 2번 정점에서 갈 수 있는 점에 대해 최솟값으로 dist를 업데이트하고, visit[2]=true로 변경한다.

1	2	3	4	5
0	2	3	7(=dist[2]+(2->4로 가는 cost) = 2+5)	INF

4. 3번 정점에서 갈 수 있는 점에 대해 최솟값으로 dist를 업데이트하고, visit[3]=true로 변경한다. 3번 정점에서 4번 정점으로 이동할 수 있지만 그 때의 비용은 3+5 = 8 이 된다. 기존의 값 7보다 크기 때문에 값이 변경되지 않는다.

1	2	3	4	5
0	2	3	7	INF

5. 1번 정점에서 5번 정점으로 갈 수 있는 경로는 존재하지 않으므로 INF값 그대로 남아있게 된다.

 

[코드 - 메모리 초과]

플로이드 와샬 알고리즘을 적용하여 해결하려 했더니 메모리 초과가 났다.

import java.util.*;

public class Main{
	static int[][] cost;
	static int n;
	static final int INF = 1000000000;
	
	
	public static void main(String[] args) {
         Scanner sc = new Scanner(System.in);
         int V = sc.nextInt();
         int E = sc.nextInt();
         int K= sc.nextInt();
         cost = new int[V+1][V+1];
         
         for(int i=1;i<=V;i++) {
        	 for(int j=1;j<=V;j++) {
        		 if(i==j)	continue;
        		 cost[i][j] = INF;
        	 }
         }
         
         for(int i=0;i<E;i++) {
        	 int u = sc.nextInt();
        	 int v = sc.nextInt();
        	 int w = sc.nextInt();
        	 
        	 cost[u][v] = Math.min(cost[u][v], w);
         }
         
         for(int k=1;k<=V;k++) {
        	
        		 for(int j=1;j<=V;j++) {
        			 cost[K][j] = Math.min(cost[K][j], cost[K][k]+cost[k][j]);
        		 }
        	 
         }
         
         for(int i=1;i<=V;i++) {
        	 if(cost[K][i]>=INF)
        		 System.out.println("INF");
        	 else
        		 System.out.println(cost[K][i]);
         }
	}
}

[최종 코드]

import java.util.*;
class Node{
	int idx;
	int cost;
	
	public Node(int idx, int cost) {
		this.idx = idx;
		this.cost = cost;
	}
}

public class Main{
	static int n;
	
	
	public static void main(String[] args) {
         Scanner sc = new Scanner(System.in);
         int V = sc.nextInt();
         int E = sc.nextInt();
         int K= sc.nextInt();
         
         boolean[] visit = new boolean[V+1];
         int[] dist = new int[V+1];
         
         ArrayList<ArrayList<Node>> graph = new ArrayList<>();
         
         for(int i=0;i<=V;i++)
        	 graph.add(new ArrayList<>());
        
         for(int i=0;i<E;i++) {
        	 int u = sc.nextInt();
        	 int v = sc.nextInt();
        	 int w = sc.nextInt();
        	 
        	 graph.get(u).add(new Node(v,w));
         }
         
         for(int i=0;i<=V;i++)
        	 dist[i] = Integer.MAX_VALUE;
         
         dist[K] = 0;
         
         
        for(int i=0;i<V;i++) {
        	int min = Integer.MAX_VALUE;
        	int idx = 0;
        	
        	for(int j=1;j<=V;j++) {
        		if(!visit[j] && dist[j] < min) {
        			min = dist[j];
        			idx = j;
        		}
        	}
        	
        	visit[idx] = true;
        	
        	for(int j=0;j<graph.get(idx).size();j++) {
        		Node node = graph.get(idx).get(j);
        		dist[node.idx] = Math.min(dist[node.idx],dist[idx]+node.cost);
        	}
        	
        }
        StringBuilder sb = new StringBuilder();
        for(int i=1;i<=V;i++) {
        	if(dist[i] >= Integer.MAX_VALUE)
        		sb.append("INF").append("\n");
        	else
        		sb.append(dist[i]).append("\n");
        }
        
        System.out.println(sb.toString());
	}
}