BOJ - 1753 최단경로

leehyunjon·2022년 4월 27일

boj 다익스트라

Algorithm

목록 보기

12/162

1753 최단경로 : https://www.acmicpc.net/problem/1753

Probelms

Solves

카카오 기출 문제 중 다익스트라를 이용한 문제가 있는걸 보았는데 다익스트라 알고리즘은 처음 들어보는 알고리즘이라 나중에 풀어보기전에 개념을 익히고자 백준 다익스트라 문제를 풀어보았다.

다익스트라(dijstra) 알고리즘이란 방향성을 가지는 그래프에서 최단거리를 구할 때 자주 사용되는 알고리즘이다.
알고리즘의 진행순서는 다음과 같다.

방문하지 않은 노드를 방문 후 방문 처리한다.
방문한 노드에서 이동할수 있는 노드를 방문한다.
시작 노드에서 방문한 노드까지의 거리와 방문한 노드에서 방문가능한 노드까지의 합이 시작 노드에서 방문한 가능한 노드까지의 거리보다 작다면 값을 갱신해주고 방문한 노드 리스트에 저장해준다.
방문한 노드 리스트 중에 거리가 가장 짧은 노드에 이동하여 방문처리한다.
더이상 방문할 노드가 없을때 까지 앞의 과정을 반복한다.

문제의 테스트케이스 예시로 알아보자.

주어진 graph를 그려보면 위의 그림과 같다.
시작점에서 부터 최단경로를 출력하는 문제임을 기억하고 위에서 설명한 다익스트라 알고리즘 진행순서대로 진행해보자.

방문하지 않는 노드 중 시작 노드를 방문 노드 리스트인 pq에 1번 노드와 거리 0을 저장한다.
이때 시작 노드에서 부터 각 노드까지의 거리는 자기자신을 제외하고 모두 INF이다.
1번 노드에서 접근가능한 2번노드, 3번 노드는 방문하지 않았고 1->2의 거리는 2, 1->3의 거리는 3이고 INF보다 작은 값이므로 pq에 2번 노드와 3번 노드를 저장한다.
pq에 저장된 값 중 2번노드의 거리가 가장 짧기 때문에 2번노드를 방문한다.
2번 노드에서 방문가능한 노드는 3번 노드와 4번 노드이다.
1->2->3의 거리는 2+4이므로 1->3(3)보다 크므로 pq에 저장되지 않는다.
1->2->4의 거리는 2+5이므로 1->4(INF)보다 작으므로 pq에 4번 노드가 저장된다.

pq값 중 거리가 작은 3을 불러오고 3번 노드는 4번 노드로만 이동이 가능하다.
하지만 1->3>->4(9)는 1->2->4(7)보다 크므로 pq에 저장되지 않는다.

pq값 중 거리가 작은 4를 불러오고 4번 노드는 이동가능한 노드가 없기 때문에 그대로끝난다.

더이상 pq에 저장된 값이 없기 때문에 반복문은 종료가된다.
그리고 1번 노드에서 각 노드로의 최단 거리는 {0, 2, 3, 7, INF}가 된다.

다익스트라를 구현할때의 시간복잡도

각 노드로의 최소 거리를 구하기 위해 각 간선을 최대 한번씩만 방문하기 때문에 O(E)
우선순위 큐를 사용했으므로 우선순위 큐의 정렬 시간복잡도는 O(ElogE)

O(E) + O(ElogE) = O(ElogE)가 된다.

Code

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

	static int INF = 100000000;
	static List<List<Node>> graph;
	static int[] distance;
	static boolean[] visit;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        //노드 갯수
		int V = Integer.parseInt(st.nextToken());
        //간선 갯수
		int E = Integer.parseInt(st.nextToken());
        //시작 정점 번호
		int K = Integer.parseInt(br.readLine());

		graph = new ArrayList<>();
        //연결 리스트 초기화
		for(int i=0;i<=V;i++){
			graph.add(new ArrayList<>());
		}

		for(int i=0;i<E;i++){
			st = new StringTokenizer(br.readLine(), " ");
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());

			graph.get(u).add(new Node(v,w));
		}

		//시작 노드에서 각 노드까지의 최단거리 저장 배열
		distance = new int[V+1];
        //노드 방문 여부확인 배열
		visit = new boolean[V+1];
		Arrays.fill(distance, INF);
        //시작 노드(자기자신)노드는 방문할수 없기 때문에 거리는 0
		distance[K] = 0;
		dijkstra(K);

		StringBuilder sb = new StringBuilder();
		for(int i = 1; i< distance.length;i++){
			int d = distance[i];
			if(d == INF){
				sb.append("INF");
			}else{
				sb.append(String.valueOf(d));
			}
			sb.append("\n");
		}
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}

	//다익스트라 함수
	static void dijkstra(int start){
    	//방문한 노드 리스트(방문 노드 중 거리가 가장 작은 값부터 가져와야하기 때문에 priorityQueue사용)
		PriorityQueue<Node> pq = new PriorityQueue<>();
		pq.offer(new Node(start, 0));

		while(!pq.isEmpty()){
			Node currentNode = pq.poll();
            //방문 노드 중 이미 방문했던 노드라면 다음 노드 탐색
			if(visit[currentNode.index]) continue;
			visit[currentNode.index] = true;

			//현재 노드에서 탐색가능한 노드 탐색
			for(Node linkedNode : graph.get(currentNode.index)){
            	//시작노드에서 현재 노드까지의 거리 + 현재 노드에서 다음 노드까지의 거리가 시작노드와의 기존 거리보다 작다면
				if(linkedNode.distance+ currentNode.distance < distance[linkedNode.index]){
                	//방문 노드 리스트에 탐색 노드와 시작노드에서 탐색 노드까지의 거리를 저장
					pq.add(new Node(linkedNode.index, linkedNode.distance+currentNode.distance));
                    //시작 노드에서 탐색 노드까지의 최단거리 갱신
					distance[linkedNode.index] = linkedNode.distance+currentNode.distance;
				}
			}
		}
	}

	static class Node implements Comparable<Node>{
		int index;
		int distance;
		public Node(int index, int distance){
			this.index = index;
			this.distance = distance;
		}

		@Override
		public int compareTo(Node o){
			return this.distance - o.distance;
		}
	}
}