[백준 JAVA] 1753번: 최단 경로

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

 

1. 인접리스트, 다익스트라

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	public static int V, E, s;
	public static int[] MIN, visited;
	public static List<Node>[] list;

	public static class Node {
		int idx;
		int cost;

		public Node(int idx, int cost) {
			super();
			this.idx = idx;
			this.cost = cost;
		}

	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		V = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());
		s = Integer.parseInt(br.readLine());
		MIN = new int[V + 1];
		visited = new int[V + 1];
		Arrays.fill(MIN, Integer.MAX_VALUE);
		list = new ArrayList[V + 1];
		for (int i = 0; i <= V; i++) {
			list[i] = new ArrayList<>();
		}

		for (int i = 0; i < E; i++) {
			st = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			int value = Integer.parseInt(st.nextToken());
			list[from].add(new Node(to, value));
		}

		Dijstra(s);

		for (int i = 1; i <= V; i++) {
			if (MIN[i] == Integer.MAX_VALUE) {
				System.out.println("INF");
			} else {
				System.out.println(MIN[i]);
			}
		}
	}

	public static void Dijstra(int start) {
		MIN[start] = 0;
		for(int v = 0; v < V; v++) {
			// step 1 : 미방문 정점 중 시작 정점에서 가장 가까운 정점 선택
			int min = Integer.MAX_VALUE;
			int minCnt = -1;
			for (int i = 1; i <= V; i++) {
				if (min > MIN[i] && visited[i] == 0) {
					min = MIN[i];
					minCnt = i;
				}
			}
			
			if(minCnt == -1) break;
			visited[minCnt] = 1;
			
			// step 2 : 선택된 정점을 경우해서 미방문 인접한 정점으로의 최소 비용을 갱신할 수 있는지 체크
			for (int i = 0; i < list[minCnt].size(); i++) {
				int to = list[minCnt].get(i).idx;
				int value = list[minCnt].get(i).cost;
				if (visited[to] == 0 && MIN[to] > MIN[minCnt] + value) {
					MIN[to] = MIN[minCnt] + value;
				}
			}
		}

	}
}

 

초기값, 시작값을 어떻게 처리해주느냐에 따라서 오류가 발생 할 수도 있음

 

또한 무한대값을 넣어주는 경우가 있는데 이럴경우 오버플로우 발생

 

step 2에서 if문에 visited[to] == 0은 사실 필요 없음 더 작을리가 없기 때문 (양의 가중치라서 그럼)

 

2. 인접리스트, 우선순위 큐, 다익스트라