웬만하면 티스토리 기록 안하고, 재밌는 강의 들으러 가려고 했는데...
다익스트라 문제는 블로그에 올린 적이 없는 것 같아서
오랜만에 개념 정리도 할 겸! 정리하고자 마음을 먹었다!
![](https://t1.daumcdn.net/keditor/emoticon/face/large/013.png)
무엇보다 내일은 5월 5일... 어린이 날이니까 ^^
시간 만땅!
1. 출처
5972번: 택배 배송
농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는
www.acmicpc.net
지금보니 시간이 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]));
}
}
}
}
}
너무 오랜만에 풀어서 까먹을 뻔한 다익스트라 ㅠ
오랜만에 만나서 반가웠다 ㅎㅎ
'알고리즘 > 백준' 카테고리의 다른 글
[MST] 백준 16202번 MST 게임 - JAVA (2) | 2023.05.13 |
---|---|
[그리디] 백준 11000번 강의실 배정 - JAVA (0) | 2023.05.05 |
[BFS] 백준 2638번 치즈 - JAVA (0) | 2023.05.03 |
[그래프] 백준 1068번 트리 - JAVA (0) | 2023.04.26 |
[BFS] 백준 1349번 숨바꼭질3 - JAVA (0) | 2023.04.24 |