BOJ 1619, 최소비용구하기

문제유형

다익스트라

문제풀이

다익스트라 기본 문제, 원리를 이해하고 풀면 좋습니다.

1. 이차원 a 배열을 생성, a값을 모두 inf(1000000000) 로 초기화
2. x,y,z 값을 입력으로 받는다. 그리고 a[x][y] 가 z보다 큰경우 값을 업데이트 한다. (작은값을 찾아야 하므로)
3. start, end를 입력으로 받는다.
4. d를 배열로 생성한다. n+1 만큼 /마찬가지로 방문여부를 확인할 수 있는 c를 n+1만큼 선언 및 초기화
5. n만큼 d에 inf 를 업데이트, n만큼 c를 false 로 업데이트
6. d[start] = 0 으로 초기화 시작지점, d의 역할은 비용 이라고 보면됀다.
7. 반복문을 n-1 만큼 순회한다.
8. 노드의 최솟지점을 찾아야 하므로 min과 x를 선언합니다. (min은 최댓값으로 x는 -1), x는 인덱스를 저장할것임
9. n만큼 순회하면서 방문하지 않은곳이고 min이 d[i] 보다 큰경우 min과 x를 업데이트 합니다.
10. 업데이트할 노드를 찾았으므로 c[x] 방문처리합니다.
11. n만큼 순회하면서 x와 연결되어있는 노선을 모두 파악해서 d[i]의 최소비용을 업데이트합니다.
    1. d[i]의 값이 d[x] + a[x][i] 보다 큰 경우 업데이트 해줍니다.
12. d[end]값을 출력해줍니다.

코드

package backjun;

import java.util.*;
import java.io.*;
public class BOJ_1916_최소비용구하기 {

	static int inf = 1000000000;
	static int[][] a = new int[1001][1001];
	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int M = Integer.parseInt(br.readLine());
		
		for(int i=0; i<a.length; i++) {
			Arrays.fill(a[i], 1000000000);
		}
		for(int i=0; i<M; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int X = Integer.parseInt(st.nextToken());
			int Y = Integer.parseInt(st.nextToken());
			int Z = Integer.parseInt(st.nextToken());
			if(a[X][Y]>Z)
				a[X][Y]=Z;
		}
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int start = Integer.parseInt(st.nextToken());
		int end = Integer.parseInt(st.nextToken());
		
		int[] d = new int[N+1];
		boolean[] c = new boolean[N+1];
		for(int i=1; i<=N; i++) {
			d[i] = inf; 
			c[i] = false;
		}
		d[start] = 0;
		for(int i=0; i<N-1; i++) {
			int min = inf+1;
			int x = -1;
			for(int j=1; j<=N; j++) {
				if(c[j]==false && min>d[j]) {
					min = d[j];
					x = j;
				}
			}
			c[x] = true;
			for(int j=1; j<=N; j++) {
				if(d[j]>d[x]+a[x][j]) {
					d[j] = d[x]+a[x][j]; //현재비용 + 간선비용 
				}
			}
		}
		System.out.println(d[end]);
	}
}