[백준 5719번] 거의 최단 경로 (java)

5719번: 거의 최단 경로

 

parent라는 ArrayList 리스트 배열을 만들어서 현재 노드의 직전 노드를 저장하는 공간을 만들어주었다.

현재 노드에 최소 경로로 도달할 수 있는 직전 노드가 여러 개 있으면, ArrayList에 여러 개를 넣는다.

 

 

예를 들어, 위의 문제 예제 그림에서 D = 6에 최소 경로로 도달할 수 있는 경우의 수는 2가지이다.

이 때 각각의 경우에서 6번 노드의 직전 노드는 3번과 5번 노드이다.

따라서 parent[6]에는 {3, 5}가 리스트로 들어있다. parent[6] = {3, 5}

 

 

이 문제의 핵심은 다익스트라 알고리즘을 2번 수행하는 것이다.

 

1. 우선 첫 번째 다익스트라를 통해 각각의 노드에 대해 최소 경로가 되는 직전 노드를 찾아서

    parent[n]에 넣어준다.

 

2. parent[n]를 통해 D에서부터 시작하여 최소 경로를 백트래킹한다.

   최소 경로에 해당하는 간선은 "거의 최단 경로"를 구할 때 사용이 불가능하다.

   따라서, 백트래킹을 하면서 최소 겨올에 해당하는 간선을 체크해야 한다.

 

   예를 들어, 위의 예제에서는 0과 1사이의 간선, 1과 5사이의 간선, 5와 6사이의 간선, 0과 3사이의 간선, 

   3과 6사이의 간선이 최소 경로에 해당한다.

   따라서 check[0][1] = true, check[1][5] = true, check[5][6] = true, check[0][3] = true, check[3][6] = true

   로 해준다.

 

   check[u][v] = true가 된 간선은, 다음 두 번째 다익스트라에서 최소 경로를 찾는 과정에서 

   사용할 수 없다.

	public static void backTracking(int S, int node) {

		if (node == S)
			return;

		for (int n : parent[node]) {

			if (!check[n][node]) {
				check[n][node] = true;
				backTracking(S, n);
			}
		}
	}

 

3. 두 번째 다익스트라를 진행한다.

   check[u][v] = false인 경로로만 최소 경로를 찾아야 하므로, 이 때 구한 최소 경로는 문제에서 요구한

   "거의 최단 경로"가 된다.

 

 

전체 코드 :