[BaekJoon] 5719 거의 최단 경로 (Java)

🔗 문제 링크

https://www.acmicpc.net/problem/5719

📝 문제풀이 방법

해당 문제는 주어진 Node들의 최단 경로를 구하는 문제가 아닌 최단 경로를 제외한 경로 중에서 최단 경로를 구하는 문제이다.

그러기 위해 먼저 최단 경로를 구하고 해당 경로를 제거를 해줘야한다.

즉, 해당 문제를 푸는데 있어서 핵심은 다익스트라(최단경로 알고리즘)를 두번 실행을 하며 그 중간에 백트래킹을 통해 경로를 제거해주는 작업을 해줘야한다.

나는 최단 경로를 알아내기 위해 parent리스트 배열을 만들어 최단 경로를 만들었을 때 각각의 node가 어떠한 node에서 왔는지를 저장하고 backtracking메서드에서 역추적으로 탐색을 해가며 해당 nodeExist의 값을 false로 바꿔주며 다음번 다익스트라에서 해당 node를 제외하도록 하였다.

👨🏻‍💻 작성한 코드

import java.io.*;
import java.util.*;

public class Main {
	static int[][] edgeInfo;
	static boolean[][] edgeExist;
	static int[] nodeArr;
	static int N;
	static List<Integer>[] parent;
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st;
		
		// 0 0이 나올때까지 test case탐색 및 수행
		String nextStr = br.readLine();
		while(!nextStr.equals("0 0")) {
			st = new StringTokenizer(nextStr);
			N = Integer.parseInt(st.nextToken());
			int M = Integer.parseInt(st.nextToken());
			
			// 출발, 도착지
			st = new StringTokenizer(br.readLine());
			int S = Integer.parseInt(st.nextToken());
			int D = Integer.parseInt(st.nextToken());
			
			
			// node들 추가
			parent = new ArrayList[N];
			nodeArr = new int[N];
			edgeInfo = new int[N][N];
			edgeExist = new boolean[N][N];
			for (int i=0; i<N; i++) {
				nodeArr[i] = Integer.MAX_VALUE;
				parent[i] = new ArrayList<>();
			}

			
			// edge추가
			for (int i=0; i<M; i++) {
				st = new StringTokenizer(br.readLine());
				int U = Integer.parseInt(st.nextToken());
				int V = Integer.parseInt(st.nextToken());
				int P = Integer.parseInt(st.nextToken());
				edgeInfo[U][V] = P;
				edgeExist[U][V] = true;
			}
	
			dijkstra(S,D);
			backTracking(S,D);

			// 첫번째 다익스트라로 나온 결과 초기화
			for (int i=0; i<N; i++) {
				nodeArr[i] = Integer.MAX_VALUE;
			}
			
			bw.write(dijkstra(S,D) +"\n");


			nextStr = br.readLine();
		}
		bw.flush();
		bw.close();
		br.close();
		
	}
	static void backTracking(int start, int now) {
		if (now == start) return;
		for (int i: parent[now]) {
			if (edgeExist[i][now]) {
				edgeExist[i][now] = false;
				backTracking(start, i);
			}
		}
	}
	
	static int dijkstra(int start, int end) {
		Queue<Integer> queue = new LinkedList<>();
		queue.add(start);
		nodeArr[start] = 0;
		
		while (!queue.isEmpty()) {
			int pop = queue.poll();
			
			for (int i=0; i<N; i++) {
				if (nodeArr[i] == nodeArr[pop] + edgeInfo[pop][i] && edgeExist[pop][i])
					parent[i].add(pop);
				else if (edgeExist[pop][i] && nodeArr[i] > nodeArr[pop] + edgeInfo[pop][i]) {
					nodeArr[i] = nodeArr[pop] + edgeInfo[pop][i];
					queue.add(i);
					parent[i].clear();
					parent[i].add(pop);
				}
			}
		}
		return nodeArr[end] != Integer.MAX_VALUE? nodeArr[end]:-1;
	}
}