<백준>
- 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] 값이 거의 최단 경로가 되고,
무한대 값이 아니라면, 출력해준다.
'모각코 > 2022_슈붕팥붕' 카테고리의 다른 글
| 6회차(01.20) - 목표 (0) | 2022.01.20 |
|---|---|
| 5회차(01.18) - 결과 (0) | 2022.01.19 |
| 5회차(01.18) - 목표 (0) | 2022.01.18 |
| 4회차(01.13) - 결과 (0) | 2022.01.13 |
| 4회차(01.13) - 목표 (0) | 2022.01.13 |