풀이 방법
다익스트라로 최단 경로를 구하는 문제이다.
최단 경로를 구하는 과정에서 지나간 지점인지 확인할 때 시야가 보이는 지점인지 확인해서 경로를 지나가지 않도록 설정하고 시야가 보이더라도 넥서스라면 경로가 지나가도록해서 최단경로를 구하도록 구현했다.
내 코드
package com.company;
import java.io.*;
import java.util.*;
class Node implements Comparable<Node> {
private int index;
private Long distance;
public Node(int index, Long distance) {
this.index = index;
this.distance = distance;
}
public int getIndex() {
return index;
}
public Long getDistance() {
return distance;
}
@Override
public int compareTo(Node other) {
if (this.distance < other.getDistance())
return -1;
return 1;
}
}
public class Main {
static ArrayList<ArrayList<Node>> graph = new ArrayList<>();
static Long[] d;
static int[] array;
static int n, m;
static void dijkstra() {
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.offer(new Node(0, 0L));
d[0] = 0L;
while (!pq.isEmpty()) {
Node node = pq.poll();
Long dist = node.getDistance();
int nowIndex = node.getIndex();
if (d[nowIndex] < dist)
continue;
for (int i = 0; i < graph.get(nowIndex).size(); i++) {
Long temp = graph.get(nowIndex).get(i).getDistance() + d[nowIndex];
if (temp < d[graph.get(nowIndex).get(i).getIndex()]
&& (array[graph.get(nowIndex).get(i).getIndex()] == 0 || graph.get(nowIndex).get(i).getIndex() == n - 1))
{
d[graph.get(nowIndex).get(i).getIndex()] = temp;
pq.offer(new Node(graph.get(nowIndex).get(i).getIndex(), temp));
}
}
}
}
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());
m = Integer.parseInt(st.nextToken());
array = new int[n];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
array[i] = Integer.parseInt(st.nextToken());
}
d = new Long[n];
Arrays.fill(d, Long.MAX_VALUE);
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<Node>());
}
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
Long t = Long.parseLong(st.nextToken());
graph.get(a).add(new Node(b, t));
graph.get(b).add(new Node(a, t));
}
dijkstra();
if (d[n - 1] == Long.MAX_VALUE)
System.out.println(-1);
else
System.out.println(d[n - 1]);
}
}
'코딩테스트 > [백준] 코딩테스트 연습' 카테고리의 다른 글
DFS와 BFS - 1260번 (0) | 2021.10.02 |
---|---|
저울 - 10159번 (0) | 2021.10.01 |
최단경로 - 1753번 (0) | 2021.10.01 |
동전 2 - 2294번 (0) | 2021.09.29 |
1로 만들기 - 1463번 (0) | 2021.09.29 |