경로 찾기 & 최단거리 -1 에서 목적지로 도달하지못할 경우와 , 계속해서 q가 쌓여 루프를 도는 문제를 해결하지못하였다.
문제를 해결하지못하여 결국 검색을 통해 찾아보았다
정답을 보면 각 경로를 구할때 무조건 큐에 쌓는것이아니라 특정 조건을 만족할때에만 큐에 쌓도록 하였는데
그 조건은 다익스트라 메소드에 시작점에서 각 정점까지 최소거리일때만 큐에 쌓는 방식을 사용한다. 이렇게되면
큐가 무한정 쌓이지않는다.
그리고 시작점에서 각 정점을 담는 배열을 Integer.MAX_VALUE로 선언한후 진행하기때문에 도착지점까지 가지못할경우 Integer.MAX_VALUE 값이 반환되고 , 이값을 최종도착지 판단 유무에 사용할 수 있다.
정답 코드
package com.myproject.CodeTest;
import java.io.*;
import java.util.*;
public class Main {
static int MAX = Integer.MAX_VALUE;
static ArrayList<Edge>[] arr ;
static int[] checkArr;
static int N;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
int E = Integer.parseInt(st.nextToken());
int length = N+1;
arr = new ArrayList[length];
int start = 1 ;
for(int i=0;i<length;i++) {
arr[i]=new ArrayList<>();
}
for(int i=0;i<E;i++) {
st =new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
arr[a].add(new Edge(b,c));
arr[b].add(new Edge(a,c));
}
st =new StringTokenizer(br.readLine());
int v1 = Integer.parseInt(st.nextToken());
int v2 = Integer.parseInt(st.nextToken());
//start -> v1 / v1 -> v2 , v2-> N
int answer1 = check(start,v1);
answer1+=check(v1,v2);
answer1+=check(v2,N);
//start -> v2 / v2 -> v1 , v1-> N
int answer2 = check(start,v2);
answer2+=check(v2,v1);
answer2+=check(v1,N);
if(Math.min(answer1, answer2)>=MAX || E==0) {
System.out.println(-1);
return;
}
System.out.println(Math.min(answer1, answer2));
}
static int check(int v1,int v2) {
checkArr=new int[N+1];
Arrays.fill(checkArr, MAX);
checkArr[v1]=0;
PriorityQueue<Edge> pq = new PriorityQueue<Edge>();
pq.add(new Edge(v1,0));
while(!pq.isEmpty()) {
Edge e1 = pq.poll();
int weight1 = e1.weight;
int dest1 = e1.dest;
if(checkArr[dest1] > weight1 ) continue;
for(int i=0;i<arr[dest1].size();i++) {
Edge e2 = arr[dest1].get(i);
int weight2 = e2.weight+weight1;
int dest2 = e2.dest;
if(checkArr[dest2] > weight2) {
checkArr[dest2]=weight2;
pq.add(new Edge(dest2,weight2));
}
}
}
return checkArr[v2];
}
}
class Edge implements Comparable<Edge> {
int dest;
int weight;
Edge(int dest,int weight){
this.dest=dest;
this.weight=weight;
}
@Override
public int compareTo(Edge o) {
// TODO Auto-generated method stub
return Integer.compare(this.weight, o.weight);
}
}
