풀이 방법
bfs를 이용해서 최단 경로를 구하는 메소드를 만들어서
1 -> v1 -> v2 -> N
1 -> v2 -> v1 -> N
두 가지 경로로 나눠서 계산해주었다.
내 코드
package com.company;
import java.io.*;
import java.util.*;
public class Main {
static int N, E, v1, v2;
static ArrayList<ArrayList<Node>> list = new ArrayList<>();
static boolean[] visited;
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());
E = Integer.parseInt(st.nextToken());
visited = new boolean[N + 1];
for (int i = 0; i <= N; i++) {
list.add(new ArrayList<>());
}
for (int i = 0; i < E; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
int z = Integer.parseInt(st.nextToken());
list.get(x).add(new Node(y, z));
list.get(y).add(new Node(x, z));
}
for (int i = 1; i <= N; i++) {
Collections.sort(list.get(i));
}
st = new StringTokenizer(br.readLine());
v1 = Integer.parseInt(st.nextToken());
v2 = Integer.parseInt(st.nextToken());
long x = bfs(1, v1);
long y = bfs(v1, v2);
long z = bfs(v2, N);
long a = bfs(1, v2);
long b = bfs(v2, v1);
long c = bfs(v1, N);
long len = Long.MAX_VALUE;
if (x != -1 && y != -1 && z != -1)
len = x + y + z;
if (a != -1 && b != -1 && z != -1)
len = Math.min(a + b + c, len);
if (len == Long.MAX_VALUE)
System.out.println(-1);
else
System.out.println(len);
}
static long bfs(int v, int N) {
if (v == N) {
return 0;
}
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.add(new Node(v, 0));
while (!pq.isEmpty()) {
Node node = pq.poll();
if (node.getDes() == N) {
Arrays.fill(visited, false);
return node.getLen();
}
if(!visited[node.getDes()]){
visited[node.getDes()] = true;
for (int i = 0; i < list.get(node.getDes()).size(); i++) {
Node a = list.get(node.getDes()).get(i);
if (!visited[a.getDes()]) {
pq.add(new Node(a.getDes(), node.getLen() + a.getLen()));
}
}
}
}
Arrays.fill(visited, false);
return -1;
}
}
class Node implements Comparable<Node> {
private int des;
private long len;
public int getDes() {
return des;
}
public Node(int des, long len) {
this.des = des;
this.len = len;
}
public long getLen() {
return len;
}
@Override
public int compareTo(Node other) {
if (this.len < other.len) {
return -1;
}
return 1;
}
}
'코딩테스트 > [백준] 코딩테스트 연습' 카테고리의 다른 글
뱀 - 3190번 (0) | 2021.11.02 |
---|---|
A -> B - 16953번 (0) | 2021.11.02 |
독서실 거리두기 - 20665번 (0) | 2021.10.27 |
뱀과 사디리 게임 - 16928번 (0) | 2021.10.27 |
택배 - 1719번 (0) | 2021.10.26 |