[JAVA] BOJ(백준) - 최단경로 - 1753

문제내용

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를 출력하면 된다.

---

문제 접근 방법

각노드까지의 최단거리를 구하는 알고리즘을 활용하면 된다.(다익스트라, 벨만포드, 플로이드워셜)

또 이문제에서 주어진 가중치는 10이하의 자연수이기 때문에 다익스트라 알고리즘을 활용하면 풀 수 있다.

다익스트라 알고리즘은 음의 가중치가 없는 그래프에서 각 노드의 최단거리를 구하는 알고리즘으로 그리디와 dp를 활용하는 알고리즘이다. 자세한 설명은 아래 블로그에 나와 있다.

https://sskl660.tistory.com/59

[Java]다익스트라 알고리즘(Dijkstra Algorithm)

만약 음의 가중치까지 주어진다면 다익스트라가 아닌 벨만포드 알고리즘으로 풀어야할 것이다.

어쨋든 이문제는 다익스트라 알고리즘으로 구현하면되는데 방법은 아래와 같다.

 

1. 인접리스트
   인접리스트를 활용해 노드간의 연결 여부를 표시한다. 즉, 그래프를 그린다고 생각하면 된다.
   참고로 방향성이 있는 그래프인지 무방향 그래프인지 확인하고 표시해주자.
   
   
2. dp배열
   각 노드에서 최소비용이 얼마인지 저장해줄 dp배열을 정의한다.
   
   
3. 우선순위 큐 활용
   위의 블로그에서 다익스트라에 대해 자세한 설명을 보면알겠지만 이 알고리즘은 2가지 방법이 존재한다.
   먼저 방문배열을 활용해 인접노드들을 돌면서 확인하는 방법이 있는데 이는 모든노드를 계속 탐색하면서 방문했는지 안했는지 따지기 때문에 O(N^2)의 시간이 걸린다.
   후에나온 우선순위큐를 활용해 구현하게 되면 O(NlogN) 시간이 걸리된다.
   따라서 현재 노드에서 연결된 인접노드들만 고려하는 우선순위큐를 활용하는게 더욱 효과적이다.

자세한 내용은 코드를 보자.

참고.
벨만 포드 : https://developer-davii.tistory.com/89
플로이드-워셜 : https://sskl660.tistory.com/61

---

풀이

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

public class Main {
	static int V, E, start;//정점, 간선, 시작정점
	static int[] dp;//dp[n번 노드] = 최소비용 -> 시작정점~n번노드까지 최소비용
	static ArrayList<ArrayList<Node1753>> list = new ArrayList<ArrayList<Node1753>>();//간선 list
	static class Node1753{//정점 번호와 비용을 알려주는 클래스
		int nodeIdx;
		int nodeCost;
		public Node1753(int nodeIdx, int nodeCost) {
			this.nodeIdx = nodeIdx;
			this.nodeCost = nodeCost;
		}
	}

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		V = Integer.parseInt(st.nextToken()); //정점 개수
		E = Integer.parseInt(st.nextToken()); //간선 개수
		start = Integer.parseInt(br.readLine()); //시작 정점
		dp = new int[V+1];
		
		//정점개수 만큼 list 방 만들기.(0은 안씀)
		for(int i=0; i<=V; i++) 
			list.add(new ArrayList<Node1753>());
		
		//dp배열 초기화
		for(int i=1; i<dp.length; i++) 
			dp[i] = Integer.MAX_VALUE; 
		
		//입력받는 간선과 비용 표시해주기
		for(int i=0; i<E; i++) {
			st = new StringTokenizer(br.readLine());
			int v1 = Integer.parseInt(st.nextToken());
			int v2 = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			
			//방향성이 있기때문에 반대는 안함
			list.get(v1).add(new Node1753(v2, c));
		}
		
		dijkStra();//다익스트라 실행
		System.out.println(printArr());//출력
		
	}
	
	//다익스트라 알고리즘으로 각 정점의 최소비용을 dp배열에 저장
	public static void dijkStra() {
		//cost기준으로 오름차순 정렬
		PriorityQueue<Node1753> pq = new PriorityQueue<Node1753>(new Comparator<Node1753>() {
			
			@Override
			public int compare(Node1753 o1, Node1753 o2) {
				int c1 = o1.nodeCost;
				int c2 = o2.nodeCost;
				
				if(c1<c2) return -1;
				else if(c1>c2) return 1;
				else return 0;
			}
		});
		
		dp[start] = 0; //시작정점에서 최소비용
		pq.add(new Node1753(start, 0)); //시작정점 정보 삽입(정점,비용)
		
		//시작정점 ~ 간선방향에 따라 연결된 모든 정점 순회
		while(!pq.isEmpty()) {
			Node1753 curN = pq.poll(); //현재 정점
			
			//현재정점의 최소비용보다 이전 정점들에서 현재정점으로 오는 비용이 더크다면 갱신할필요 없음
			//즉, 갱신할지 말지 for문을 통해 검사할 필요가 없음.
			//최소비용을 뽑는 문제임.
			if(dp[curN.nodeIdx] < curN.nodeCost) continue;  
			
			
			//현재 뽑은 노드와 연결된 인접노드를 탐색
			for(int i=0; i<list.get(curN.nodeIdx).size(); i++) {
				//인접노드
				Node1753 nextN = list.get(curN.nodeIdx).get(i);
				
				//인접노드까지의 거리가 dp에 저장된 최소비용보다 작으면 인접노드에 대한 최소비용을 갱신
				if(dp[nextN.nodeIdx] > curN.nodeCost + nextN.nodeCost) {
					//최소비용 갱신
					dp[nextN.nodeIdx] = curN.nodeCost + nextN.nodeCost;
					
					//인접노드의 번호와 그 노드까지의 최소비용 넣기
					pq.add(new Node1753(nextN.nodeIdx, dp[nextN.nodeIdx]));
				}
			}
		}
	}
	
	public static String printArr() {
		StringBuilder sb = new StringBuilder();
		for(int i=1; i<dp.length; i++) {
			if(dp[i]==Integer.MAX_VALUE) sb.append("INF").append("\n");
			else sb.append(dp[i]).append("\n");
		}
		return sb.toString();
	}
}

---

마치며

처음으로 다익스트라 알고리즘을 구현해 본 문제이다. 다익스트라에 대한 개념만 어렴풋이 알고있었는데 이번기회에 좀더 자세히 공부할수 있었고 어떤 상황에 쓰이는지도 공부 할 수 있었던 문제이다.
더 많은 문제를 풀어볼 필요가 있다고 느낀다.