[백준 문제 풀기] 1753번: 최단 경로 (다익스트라, 자바)
2020. 6. 15. 23:56
반응형
문제 : https://www.acmicpc.net/problem/1753
문제
방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 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 |
사용 알고리즘
다익스트라
코드 (자바)
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws Exception{
// 입력 값 셋팅
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int V, E; // 정점의 수, 간선의 수
int K; // 시작 정점
V = Integer.parseInt(st.nextToken());
E = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
K = Integer.parseInt(st.nextToken());
ArrayList<int[]>[] G = new ArrayList[V+1]; // 그래프 생성
for (int i=1 ; i <=V ; i++) {
G[i] = new ArrayList<int[]>();
}
// 그래프에 값 입력
for (int i=1 ; i <=E ; i++) {
st = new StringTokenizer(br.readLine());
int[] tempEdge = new int[3];
tempEdge[0] = Integer.parseInt(st.nextToken()); // 시작 정점
tempEdge[1] = Integer.parseInt(st.nextToken()); // 종료 정점
tempEdge[2] = Integer.parseInt(st.nextToken()); // 간선 가중치
G[tempEdge[0]].add(tempEdge); // 시작 정점의 번호 그래프에 경로 정보 저장
}
int[] dist = new int[V+1]; // 시작점에서 각 정점까지의 거리를 저장할 배열
boolean[] isVisited = new boolean[V+1]; // 방문 여부 기록
PriorityQueue<Info> pq = new PriorityQueue<Info>(new Comparator<Info>() { // 거리가 짧은 목적지를 가져오기 위한 우선순위큐. 거리순으로 오름차순 정렬
@Override
public int compare(Info o1, Info o2) {
// TODO Auto-generated method stub
return o1.dist - o2.dist;
}
});
// 거리배열 초기화
Arrays.fill(dist, Integer.MAX_VALUE);
dist[K] = 0; // 시작점의 거리를 0 으로 설정
// System.out.println(Arrays.toString(dist));
// 우선순위큐 값 입력
for (int i=1;i<=V;i++) {
if (i==K) {
pq.add(new Info( K, 0 )); // 시작점일 경우 dist =0
}else {
pq.add(new Info(i, Integer.MAX_VALUE)); // 시작점을 제외하고 무한대 입력
}
}
// 다익스트라 시작
/*
* 우선순위 큐에서 poll()
* 뽑아온 정점에 연결된 모든 정점에 대해서 기존 dist 배열에 저장된 값과 비교해서 dist 가 작은 경우를 제외하고 업데이트 후 pq 에 add
* 큐가 빌 때 까지 계속 연산
*/
while(!pq.isEmpty()) {
Info tempInfo = pq.poll();
if (isVisited[tempInfo.index] == false) {
isVisited[tempInfo.index]= true;
if (dist[tempInfo.index] >= tempInfo.dist) { // dist 배열에 있는 값이 큐에서 가져온 값보다 크거나 같은 경우 연산함
dist[tempInfo.index] = tempInfo.dist;
// 방문하지 않은 연결된 정점에 대해서 dist 만큼 더해서 pq 에 add
for (int i=0 ; i < G[tempInfo.index].size() ; i++) {
// G[i] -> int[2] 이고
// System.out.println(G[tempInfo.index].get(i)[0]);
// G[tempInfo.index].get(i)[0];
if (isVisited[G[tempInfo.index].get(i)[1]] == false ) {
pq.add((new Info (G[tempInfo.index].get(i)[1] , G[tempInfo.index].get(i)[2] + tempInfo.dist)));
}
}
}
}
}
// System.out.println();
// 다익스트라 종료
// 답 출력
for (int i = 1 ; i< dist.length ; i++) {
if (dist[i] == Integer.MAX_VALUE) {
System.out.println("INF");
}else {
System.out.println(dist[i]);
}
}
}
// 정점을 뽑아오기 위한 우선순위큐를 선언하기 위한 클래스
static class Info {
int index;
int dist;
public Info (int index, int dist) {
this.index = index;
this.dist = dist;
}
}
}
/* [인터돌™] 공부 해보자!! 열심히~~~ http://globalhost.tistory.com */
다익스트라 알고리즘의 가장 기본적인 문제
이 글을 공유합시다
