[다익스트라] 백준 5972번 택배 배송 - JAVA

웬만하면 티스토리 기록 안하고, 재밌는 강의 들으러 가려고 했는데...

다익스트라 문제는 블로그에 올린 적이 없는 것 같아서

오랜만에 개념 정리도 할 겸! 정리하고자 마음을 먹었다!

 

무엇보다 내일은 5월 5일... 어린이 날이니까 ^^

시간 만땅!

 

 

---

1. 출처

---

 

5972번: 택배 배송

 

지금보니 시간이 1초가 아슬아슬하게 풀었구나 싶다 ... ㅎㅎ...

 

 

 

---

2. 설계

---

 

1. 헛간 연결 상태를 입력받고 양방향으로 연결해준다.

for(int i=0;i<M;i++) {
	int path1 = sc.nextInt();
	int path2 = sc.nextInt();
	int cow = sc.nextInt();
	adjList[path1].add(new Node(path2, cow));
	adjList[path2].add(new Node(path1, cow));
}

 

 

2. 각 헛간에 도착할 때 만날 수 있는 최소 소의 수는 몇인지 계산해준다. (다익스트라)

public static void dijkstra() {
		PriorityQueue<Node> q = new PriorityQueue<>();
		boolean[] visited = new boolean[N+1];
		
		q.add(new Node(1,0));
		dist[1]=0;
		
		while(!q.isEmpty()) {
			Node cur = q.poll();
			
			visited[cur.num]=true;//큐에서 나오는 순간 이 길을 선택한 것임
			
			for(int i=0;i<adjList[cur.num].size();i++) {
				Node next = adjList[cur.num].get(i);
				
				if(visited[next.num]) continue;//이미 선택된 길을 또 선택하지 않는다.
				
				
				if(dist[next.num]>dist[cur.num]+next.cow) {
					dist[next.num]=dist[cur.num]+next.cow;
					q.add(new Node(next.num,dist[next.num]));
				}
			}
		}

- 농부 현서가 1번 헛간에서부터 진행하기 때문에 1번 헛간부터 시작한다.

1번 헛간에서 만날 수 있는 소는 0마리이다. (dist[1] = 0)

 

- 가장 최소거리를 가진 큐(헛간)을 꺼내 길로 채택하고, 해당 헛간과 연결된 양방향 헛간을 검사한다.

가장 최소 거리가 큐에서 나왔다면 그 헛간을 가겠다고 채택한 것이므로 visited[헛간번호]=true로 해준다.

연결된 헛간 중 이미 채택된 헛간은 선택하지 않는다. (2번 가지 않겠다.) 

현재까지 만난 소 (dist[next.num])보다 내가 지금 만나고 온 소와 지금 가려고 하는 길에 있는 소를 합친 게 더 많다면 dist[next.num]을 갱신해준다.

 

- 최소 거리가 갱신되었다면, 큐에 넣어준다.

 

 

---

3. 전체 코드

---

 

package 백준5972;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;

public class 택배배송 {
	
	static int[] dist;
	static List<Node>[]adjList;
	static int N,M;
	
	static class Node implements Comparable<Node>{
		int num;
		int cow;
		public Node(int num, int cow) {
			super();
			this.num = num;
			this.cow = cow;
		}
		@Override
		public int compareTo(Node o) {
			return this.cow>o.cow?1:-1;
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();//헛간수
		M = sc.nextInt();//소들의 길, 양방향 길
		
		//초기화
		dist = new int[N+1];//N번 헛간까지 가는 최소의 여물
		for(int i=0;i<N+1;i++) {
			dist[i]=Integer.MAX_VALUE;
		}
		
		adjList = new ArrayList[N+1];
		for(int i=0;i<N+1;i++) {
			adjList[i] = new ArrayList<>();
		}
		
		for(int i=0;i<M;i++) {
			int path1 = sc.nextInt();
			int path2 = sc.nextInt();
			int cow = sc.nextInt();
			adjList[path1].add(new Node(path2, cow));
			adjList[path2].add(new Node(path1, cow));
		}
		
		//입력끝
		
		dijkstra();


		System.out.println(dist[N]);
	}
	
	public static void dijkstra() {
		PriorityQueue<Node> q = new PriorityQueue<>();
		boolean[] visited = new boolean[N+1];
		
		q.add(new Node(1,0));
		dist[1]=0;
		
		while(!q.isEmpty()) {
			Node cur = q.poll();
			
			visited[cur.num]=true;//큐에서 나오는 순간 이 길을 선택한 것임
			
			for(int i=0;i<adjList[cur.num].size();i++) {
				Node next = adjList[cur.num].get(i);
				
				if(visited[next.num]) continue;//이미 선택된 길을 또 선택하지 않는다.
				
				
				if(dist[next.num]>dist[cur.num]+next.cow) {
					dist[next.num]=dist[cur.num]+next.cow;
					q.add(new Node(next.num,dist[next.num]));
				}
			}
		}
		
	}

}

 

 

 

---

너무 오랜만에 풀어서 까먹을 뻔한 다익스트라 ㅠ

오랜만에 만나서 반가웠다 ㅎㅎ