[Algorithm] 백준 1753 최단경로 - 다익스트라 알고리즘

지난주 스터디에서 그래프를 공부했다고 실버 안풀어보고 덤볐다가 시간초과때매 두시간동안 고생했다ㅜ0ㅜ

까먹기 전에 정리해서 이제 똑같은 이유로는 안틀릴거다☠️

---

문제

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 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를 출력하면 된다.

---

풀이

• 가중치까지 리스트에 함께 저장해줘야하므로 정점과 가중치를 함께 저장할 수 있는 클래스를 만들어서 사용했다
• 인접행렬을 사용하면 메모리초과가 발생하므로 인접리스트에 간선 정보를 저장한다
• 가중치가 작은 노드들부터 꺼내서 검사하기 위해 우선순위 큐를 사용해야한다
• 우선수위 큐에 들어가는 객체가 사용자 클래스 타입이므로 Comparable 또는 Comparator를 사용해 정렬 기준을 만들어줘야한다
• 시작노드를 큐에 넣어주고 탐색을 시작한다 -> 직접 인접한 노드들과 인접노드들과 인접한 노드들까지 큐에 넣어가며 모두 탐색한다!

시간초과 해결 ⏰

• ❌원래는 Scanner를 이용해서 입력을 받았다
• ⭕️간선이 최대 300,000개까지 입력이 들어올 수 있으므로 BufferedReader를 이용해 입력을 받도록 수정하였다
• ❌queue를 이용해서 푸는 방식이니까 bfs에서 하는것처럼 visit배열을 만들어 방문 여부를 체크해줬었다
• ⭕️bfs에서 쓰는것처럼 while문 만에서 continue를 걸어줄 시 한번 거리를 갱신한 후에는 다시 해당 정점을 탐색하지 못하므로 더 짧은 거리로 업데이트를 해줄수가 없다!!
• ❌ (전에 어디선가 빠르다고 봤던게 기억나서) LinkedList를 이용해 인접리스트를 만들어줬었다
• ⭕️리스트의 값들을 삽입 또는 삭제할 때는 LinkedList가 빠르고, 값을 조회할 때는 ArrayList가 훨씬 빠르다! 이 문제에서는 while문에서 계속 node를 조회해줘야하므로 ArrayList를 사용하는 것이 훨씬 시간 효율성이 좋다 
• ⭕️각 정점과 인접한 노드의 수는 정점마다 다르지만, 정점 개수는 입력시 정해진 값에서 달라지지않으므로 ArrayList 타입의 배열을 사용해줬다 (static ArrayList<Node>[] list;)
• ❌큐에 다 넣고 탐색한다
• ⭕️인접 노드의 최단경로가 현재 노드의 최단경로 + 인접 노드까지의 가중치 보다 작으면 현재 배열에 저장된 값이 최단경로이므로 값을 갱신해줄 필요가 없다

코드

package week6;

import java.io.*;
import java.util.*;

class Node{
	int idx, weight;
	public Node(int idx, int weight) {
		this.idx = idx;
		this.weight = weight;
	}
}

public class BOJ1753 {
	static int v, e, start, INF=987654321;
	static int[] dist;
	static ArrayList<Node>[] list;
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] st = br.readLine().split(" ");
		v = Integer.parseInt(st[0]);
		e = Integer.parseInt(st[1]);
		list = new ArrayList[v+1];
		dist = new int[v+1];
		start = Integer.parseInt(br.readLine());
		for (int i = 0; i <= v; i++) {
			dist[i] = INF;
			list[i] = new ArrayList<Node>();
		}
		for(int i=0; i<e; i++) {
			st = br.readLine().split(" ");
			int v1 = Integer.parseInt(st[0]);
			int e1 = Integer.parseInt(st[1]);
			int w = Integer.parseInt(st[2]);
			list[v1].add(new Node(e1, w));
		}
		
		getResult();
		
		for(int i=1; i<dist.length; i++) {
			if(dist[i]==INF) sb.append("INF" + "\n");
			else sb.append(dist[i] + "\n");
		} System.out.print(sb.toString());
	}
	
	static void getResult() {
		// 가중치가 작은 순서로 정렬하기 위해 우선순위 큐 사용
		PriorityQueue<Node> pQueue = new PriorityQueue<Node>( new Comparator<Node>() {
			@Override
			public int compare(Node o1, Node o2) { // 정렬 기준 정의
				return o1.weight-o2.weight;
			}
		});
		dist[start] = 0;
		pQueue.add(new Node(start, 0)); // 시작 노드를 큐에 넣어줌
		
		while (!pQueue.isEmpty()) {
			Node nowNode = pQueue.poll();
			
			for(Node node : list[nowNode.idx]) { // 현재 노드와 인접한 노드 탐색
				if(dist[node.idx] > dist[nowNode.idx]+node.weight) { // 인접 노드까지의 경로가 현재 노드+인접노드 가중치보다 크다면
					dist[node.idx] = dist[nowNode.idx]+node.weight; // 가중치 재정의
					pQueue.offer(new Node(node.idx, dist[node.idx])); // 인접 노드를 큐에 넣어줌
				}
			}
		}
	}
}

---

간단하고 익숙해진 자료구조만 쓰려고 하는 습관이 있는데, 입출력 조건을 잘 보고 문제마다 최적의 효율을 낼 수 있는 자료구조를 쓸 수 있도록 연습을 많이 해야겠다🥊