[백준] 골드4 1753번 최단경로 完

 

[백준] 골드4 1753번 최단경로

1753번: 최단경로

시간 제한: 1초

메모리 제한: 256MB

---

 

문제

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

---

Ⅰ문제 분석하기

( 해당 분석은 예제 번호 2번을 기반으로 작성되었습니다. )

[그림 1]

 

V의 범위가 1부터 2만까지, E의 범위가 1부터 30만까지임으로 2차원배열로 해당정보를 저장할 경우 메모리 초과가 발생할 수 있습니다. 따라서 ArrayList를 생성하여 정보를 관리합니다.

입력값을 아래와 같은 형식으로 V에서 E로 가는 각각의 거리를 저장합니다.

리스트	노드
1 V	1V에서 2V까지의 거리 [ 2 ]	1V에서 3V까지의 거리 [ 3 ]
2 V	2V에서 3V까지의 거리 [ 4 ]	2V에서 4V까지의 거리 [ 5 ]
3 V	3V에서 4V까지의 거리 [ 6 ]
4 V
5 V	5V에서 1V까지의 거리 [ 1 ]

 

그리고 시작점에서 각 정점까지의 최소값을 저장하기 위한 배열 ANS를 선언합니다. 최소값을 앞으로 저장할 것이기때문에 초기값은 MAX_VALUE 로 선언해줍니다. 그리고 시작점에서 시작점까지는 언제나0이기때문에, 0으로 지정해줍니다.

배열 번호	0 (1번 노드까지)	1 (2번 노드까지)	2  (3번 노드까지)	3 (4번 노드까지)	4 (5번 노드까지)
저장 값	시작점에서 1V까지의 최소 거리 [ MAX_VALUE ]	시작점에서 2V까지의 최소 거리 [ 0 ]	... [ MAX_VALUE ]	... [ MAX_VALUE ]	... [ MAX_VALUE ]

 

이제 최소 거리를 찾아내는 알고리즘인데요, 이러한 알고리즘에서 우리는 PriorityQueue (우선순위 큐)를 사용할 수 있습니다. 우선순위 큐란 우선순위가 높은 데이터가 먼저 나가는 자료구조입니다.

이번 문제에서는 우선순위 큐에 [ 정점 V의 번호, 시작점에서 정점까지의 가중치 ] 를 노드로 넣어 작은 값의 가중치가 우선 출력되도록 구현해보겠습니다.

 

 

[ 시작점의 번호(이번 예제에서는 2), 시작점에서 시작점까지의 가중치(언제나 0) ] 를 우선순위 큐에 삽입합니다.

[그림 2]

이후 우선순위 큐가 빌 때까지 아래의 순서를 반복합니다.

   ① 우선순위 큐 중 가장 가중치가 작은(=우선순위가 높은) 값의 노드를 꺼낸다 

[그림 3]

   ② 꺼낸 노드의 리스트를 가져와 하나씩 현재의 최소값과 비교합니다. 다음 노드를 거쳐서 가는 것이 더욱 빠를 경우, 다음 노드를 우선순위 큐에 넣고 최소값을 보관하는 ANS배열을 갱신해줍니다.

[그림 4]

      

[그림 5]

---

  [ While 반복 부분 ]

   ① 우선순위 큐 중 가장 가중치가 작은(=우선순위가 높은) 값의 노드를 꺼낸다

   ② 꺼낸 노드의 리스트를 가져와 하나씩 현재의 최소값과 비교합니다.

        해당 노드를 거쳐 가는 것이 더욱 느리기 때문에 값을 갱신하지 않는다.

 

[그림 6]

---

  [ While 반복 부분 ]

   ① 우선순위 큐 중 가장 가중치가 작은(=우선순위가 높은) 값의 노드를 꺼낸다

 

---

이제 모든 최소 거리의 탐색이 종료되었습니다. 지금까지 저장한 답안을 출력하고 프로그램을 종료합니다.

배열 번호	0 (1번 노드까지)	1 (2번 노드까지)	2  (3번 노드까지)	3 (4번 노드까지)	4 (5번 노드까지)
저장 값	[ MAX_VALUE ]	[ 0 ]	[ 4 ]	[ 5 ]	[ MAX_VALUE ]

---

Ⅱ 슈도코드 작성하기

/*
* 작성자, 1.0, 2024.02.02 누Ring <dierdia@naver.com>
*
* BAEKJOON 골드4 1753 최단경로
* 문제 링크: https://www.acmicpc.net/problem/1753
* 작성 언어: Pseudo-code
*/


[compareTo를 override할 Class Node 선언]
   [정수] 정점의 번호 v
   [정수] 가중치 cost
   [this를 사용하기 위한 함수]
   [Override compareTo 함수]

/* Main */
[정수 입력] 정점의 개수 V 
[정수 입력] 간선의 개수 E
[정수 입력] 시작점 K

[배열 선언] 답안을 저장할 ans
for(정점 V의 개수만큼){
   ans 값을 MAX_INTEGER 값으로 초기화
}
ans[시작점 K] = 0으로 초기화(자기자신에서 자기자신으로 가는 거리는 0)

[ArrayList 선언] list
for(정점 V의 개수만큼){
   ArrayList 초기화
}

for(간선 E의 개수만큼){
   [정수 입력] 시작 노드번호 u
   [정수 입력] 도착 노드번호 v
   [정수 입력] 가중치 c
   [ArrayList 추가] u의 리스트를 가져와 (v,c)노드를 삽입
}

[우선순위큐 선언] PQ
[큐에 노드 삽입] (시작점K, 0)
while(PQ가 빌 때까지){
   [PQ값 꺼내기] now
   for(now.v의 ArrayList 개수만큼 반복, ArrayList에서 노드번호와 가중치를 가져옴){
       if(ans에 저장된 값 보다 가져온 노드 번호를 거쳐서 가는게 빠를 경우){
           [ans갱신]
           [PQ값 넣기] (다음 노드 번호 V, 가중치 C)
       }
   }
}

for(정점 V의 개수만큼){
    if(ans[v]가 MAX_INTEGER이면){
        [출력] "INF"
    }
    else{
        [출력] ans[v]
    }
}

---

Ⅲ 코드 구현 ( 구현 언어: JAVA )

/*
* 작성자, 1.0, 2024.02.02 누Ring <dierdia@naver.com>
*
* BAEKJOON 골드4 1753 최단경로
* 문제 링크: https://www.acmicpc.net/problem/1753
* 작성 언어: JAVA
*/

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

public class Main {
	static class Node implements Comparable<Node>{
		int v; // 정점의 번호
		int cost; // 정점의 가중치
		
		public Node(int v, int cost)
		{
			this.v=v;
			this.cost=cost;
		}
		
		@Override
		public int compareTo(Node n)
		{   // 작은 비용이 우선되도록
			return this.cost - n.cost;
		}
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st= new StringTokenizer(br.readLine());
		
		int V = Integer.parseInt(st.nextToken()); // 1 ≤ V ≤ 20,000      정점의 개수
		int E = Integer.parseInt(st.nextToken()); // 1 ≤ E ≤ 300,000    간선의 개수
		int ST = Integer.parseInt(br.readLine()); // 시작 정점
		
		/*Array List 선언 및 초기화*/
		ArrayList<ArrayList<Node>> list = new ArrayList<ArrayList<Node>>();
        for(int i=0;i<=V;i++)
		{
			list.add(new ArrayList<Node>());
		}
		
        /* 간선값 입력 */
		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 w=Integer.parseInt(st.nextToken());
			list.get(v1).add(new Node(v2, w));
		}
		
		//각 정점까지의 최소값을 저장하기 위한 배열 선언 및 초기화
		int ans[] = new int[V+1]; 
		for(int i=0;i<V+1;i++)
		{
			ans[i]=Integer.MAX_VALUE;
		}
		ans[ST]=0;
		
		PriorityQueue<Node> pq = new PriorityQueue<>();
		pq.add(new Node(ST,0));
		while(!pq.isEmpty())
		{
			Node now = pq.poll();
			for(Node next:list.get(now.v))
			{
                if(ans[next.v]>ans[now.v]+next.cost) // 다음걸 거쳐서 가는게 더욱 빠를 경우만 진행
				{
					ans[next.v]=ans[now.v]+next.cost;
					pq.add(new Node(next.v,ans[next.v]));
				}			
   			}	
		}
		
        /*양식에 맞게 답안 출력*/
		for(int i=1;i<=V;i++)
		{
			if(ans[i]==Integer.MAX_VALUE)
			{
				System.out.println("INF");
			}
			else
			{
				System.out.println(ans[i]);
			}
		}
	}
}