/ BOJ

BOJ_1753_최단경로_JAVA

문제 : 최단경로

링크 : BOJ_1753_최단경로

접근 방식

다익스트라 알고리즘을 이용해야하는 문제이다.

한 노드에서 다른 노드로 이동하는 모든 최단경로를 구해야한다. 먼저 다익스트라 알고리즘에 대해 알아보겠다.

다익스트라(Dijkstra) 알고리즘은 하나의 시작 정점에서 다른 모든 정점의 최단경로를 구하는 알고리즘이다. 특징으로는 그리디한 기법을 사용해 지나간 길을 다시 돌아가는 작업을 거치지 않기 때문에 간선의 가중치가 음수인 경우는 고려하지 않는 것이다.

최소신장트리의 프림(Prim’s) 알고리즘과 유사하다.

적용 방법은 다음과 같다.

  1. 먼저 모든 정점의 거리 정보를 1차원 배열에 저장한다. 이에대한 전제조건으로 그래프로 주어지는 인접행렬 간선이 주어진 부분이 아니면 전부 무한대로 초기화 되어있다고 가정한다. 다만, 0으로 초기화되어있다고 하더라도 기본적으로 해당 1차원 배열에 대해 정점에서 값을 얻어오지 않고 무한대로 처음부터 초기화 해두는 방법도 있다.

  2. 시작 정점을 하나 선택하고 해당 정점에 대한 거리 배열을 0으로 만든다. 이것에 대한 의미는, a 정점을 선택했다고 하면, a->a로 이동하는 최단 거리가 0임을 뜻한다.

  3. a를 방문처리하고, 거리 배열에서 a와 연결된 노드들을 a에서 해당 노드로 이동하는 가중치 값으로 변경시켜준다.

  4. a와 연결된 간선중 아직 방문하지 않았으면서 거리가 최소인 노드를 찾는다. 그 후 해당 노드를 방문처리한다.(노드 이동)

  5. 현재 거리 배열에 있는 값과, 현재 연결한 노드 + 그 노드로부터 연결되어있는 간선의 거리 중 더 짧은 거리를 거리 배열 전체를 돌면서 집어넣는다.

  6. 4~5 의 과정을 노드 개수만큼 반복한다.

위 과정을 통해 다익스트라 알고리즘, 한 노드에서 다른 모든 노드에게로의 최단 거리가 구해지게 된다.

소스 코드


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ_1753_최단경로 {
	static int V,E,K,arr[][];

	public static void main(String[] args) throws IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(in.readLine()," ");

		V = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());

		K = Integer.parseInt(in.readLine());
		// 정점 정보
		arr = new int[V+1][V+1];

		// 정점에 값 집어넣기
		for(int i=0;i<E;i++) {
			st = new StringTokenizer(in.readLine()," ");

			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			arr[from][to] = Integer.parseInt(st.nextToken());
		}



		int[] answer = dijkstra(K);

		for(int i=1;i<=V;i++) {
			if(answer[i] == Integer.MAX_VALUE) {
				System.out.println("INF");
			}else {
				System.out.println(answer[i]);
			}
		}
	}

	public static int[] dijkstra(int start) {
		// 거리 배열 생성 : 정점 개수만큼
		int[] distance = new int[V+1];

		// 방문 정보 저장
		boolean[] visited = new boolean[V+1];

		// 거리 배열 초기화
		Arrays.fill(distance, Integer.MAX_VALUE);

		// 시작 정점의 거리를 0으로 만듦
		distance[start] = 0;

		//정점 개수만큼 반복
		for(int i=0;i<V;i++) {
			int min = Integer.MAX_VALUE;
			int current = 0;

			// 해당 노드로부터 연결되어있는 다음 노드로의 최솟값 구하기
			for(int j =0 ;j<V;j++) {
				if(!visited[j] && min > distance[j]) {
					min = distance[j];
					current = j;
				}
			}

			// 해당 노드를 방문처리
			visited[current] = true;

			// 현재 거리 배열에 저장되어있는 값, 현재 노드까지의 거리 + 앞으로 이동할 노드의 거리 중 더 작은 값을
			// 거리 배열의 해당 노드에 넣는다.
			for(int j=0;j<V;j++) {
				// 아직 방문하지 않았고, 간선이 연결되어있으며 두 개의 거리 중 더 작은 값을 할당한다.
				if(!visited[j] && arr[current][j] != 0 &&
					distance[j] > distance[current] + arr[current][j]) {
						distance[j] = distance[current] + arr[current][j];
					}
			}
		}

		return distance;
	}

}