6회차(01.20) - 결과

<백준>

- Java

---

* 거의 최단 경로

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	
	static int N,M;
	static int S,D;
	static ArrayList<Info>[] map;
	static ArrayList<Integer>[] tracking;
	static boolean[][] isShortest; //true면 a>b가 최단
	static int[] distance;
	static final int INF = Integer.MAX_VALUE;
	
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		
		while(true) {
			st = new StringTokenizer(br.readLine()," ");
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			
			if(N==0 && N==0) break;
			
			st = new StringTokenizer(br.readLine()," ");
			S = Integer.parseInt(st.nextToken());
			D = Integer.parseInt(st.nextToken());
			
			map = new ArrayList[N+1];
			tracking = new ArrayList[N+1];
			distance = new int[N+1];
			isShortest = new boolean[N+1][N+1];
			
			for(int i =0; i<N; i++) {
				map[i] = new ArrayList<>();
			}
			
			int u,v,p;
			for(int i=1; i<=M; i++) {
				st = new StringTokenizer(br.readLine()," ");
				u = Integer.parseInt(st.nextToken());
				v = Integer.parseInt(st.nextToken());
				p = Integer.parseInt(st.nextToken());
				map[u].add(new Info(v,p));
			}
			dijkstra(S);
			if(distance[D]==INF) {
				bw.write("-1"+"\n");
				continue;
			}
			backTracking(D,S);
			dijkstra(S);
			
			if(distance[D]==INF) {
				bw.write("-1"+"\n");
			}else {
				bw.write(distance[D]+"\n");
			}
		
		}
		bw.flush();
		bw.close();
	}
	
	//D에서 S방향으로 tracking을 수행 -> backtracking
	static void backTracking(int now, int end) { //false를 찾아 true로 바꿔줌
		if(now == end) return;
		
		for(int next : tracking[now]) {
			if(isShortest[next][now] == false) {
				isShortest[next][now] =true;
				backTracking(next,end);
			}
		}
	}
	
	static void dijkstra(int s) {
		for(int i =0;i<N; i++) { //다익스트라를 두번 돌릴 예정이라 여기서 초기화해줌
			tracking[i] = new ArrayList<>();
		}
		Arrays.fill(distance,INF);
		
		PriorityQueue<Info> pq = new PriorityQueue<>();
		distance[s]=0; 
		pq.add(new Info(s,0));
		
		while(pq.isEmpty()==false) {
			Info now = pq.poll();
			
			if(now.distance > distance[now.node]){ //더 큰 거리면 패스
				continue;
			}
			
			for(Info next : map[now.node]) {
				if(isShortest[now.node][next.node]==false) {//2번째 다익스트라를 튀함으로 true인경우 pass
					if(distance[next.node]>distance[now.node]+next.distance) { //다음 노드보다 작은 경우
						distance[next.node]=distance[now.node]+next.distance;
						//새로운 distance 이므로 clear 후 add. 
						tracking[next.node].clear(); 
						tracking[next.node].add(now.node);
						pq.add(new Info(next.node, distance[next.node]));
					}else if(distance[next.node]==distance[now.node]+next.distance){
						//모든 최단경우를 tracking에 넣어줘야하기때문에 같은 경우 넣어줌
						tracking[next.node].add(now.node);
					}
				}
			}
		}
		
	}
}

class Info implements Comparable<Info>{
	int node;
	int distance;
	
	public Info(int node, int distance) {
		this.node = node;
		this.distance = distance;
	}
	
	@Override
	public int compareTo(Info o) {
		return Integer.compare(distance,o.distance);
	}
}

 

가장 최단인 경우가 아닌, 거의 최단 경로라 두 번째 짧은걸 찾아야 한다.

따라서 다익스트라를 두번 수행한다.

다익스트라, 백트래킹, 다익스트라.

이렇게 수행하게 된다.

 

백트래킹의 경우는 D-> S 로 가면서, 즉 뒤에서 앞으로 가면서

false인거 발견하면 true로 바꾸고, 재귀로 이를 반복하며 앞으로 가다가,

now가 end가 되면 끝! 이다.

 

다익스트라의 경우는 우선 초기화를 진행한다.

다익스트라를 두 번 진행할 것이기 때문에 먼저 tracking배열을 초기화 해준다.

우선순위 큐를 활용 하기 위해 하나 생성해 준다.

그리고 시작점을 0으로 설정 후 큐에 추가 !

이제 큐가 빌때까지 반복!

최단경우를 tracking에 넣어주는 작업을 수행한다.

 

이제 distance[D] 값이 거의 최단 경로가 되고, 

무한대 값이 아니라면, 출력해준다.