August 04, 2022
백준 문제 링크 : https://www.acmicpc.net/problem/12834
package backjoon.P12834;
import java.io.*;
import java.util.*;
import java.util.stream.Collectors;
public class Main {
static class Node {
public int v, dis;
public Node(int v, int dis) {
this.v = v;
this.dis = dis;
}
}
public static void main(String[] args) throws Exception {
System.setIn(new FileInputStream("src/backjoon/input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int V = Integer.parseInt(st.nextToken());
int E = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
int kist = Integer.parseInt(st.nextToken());
int food = Integer.parseInt(st.nextToken());
List<Integer> people = Arrays.stream(br.readLine().split(" "))
.map(Integer::parseInt)
.collect(Collectors.toList());
ArrayList<Node>[] graph = new ArrayList[V + 1];
//Arrays.fill(graph, new ArrayList<>()); // Arrays.fill 함부로 쓰지 말기
for (int i = 0; i < graph.length; i++) {
graph[i] = new ArrayList<>();
}
for (int i = 0; i < E; i++) {
st = new StringTokenizer(br.readLine());
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
int dist = Integer.parseInt(st.nextToken());
graph[s].add(new Node(e, dist));
graph[e].add(new Node(s, dist));
}
int[] kistDis = new int[V + 1];
int[] foodDis = new int[V + 1];
Arrays.fill(kistDis, Integer.MAX_VALUE);
Arrays.fill(foodDis, Integer.MAX_VALUE);
PriorityQueue<Node> pq = new PriorityQueue<>((n1, n2) -> n1.dis - n2.dis);
kistDis[kist] = foodDis[food] = 0;
pq.add(new Node(kist, 0));
while (!pq.isEmpty()) {
Node cur = pq.poll();
if (kistDis[cur.v] < cur.dis)
continue;
for (Node n : graph[cur.v]) {
if (kistDis[n.v] > kistDis[cur.v] + n.dis) {
kistDis[n.v] = kistDis[cur.v] + n.dis;
pq.add(new Node(n.v, kistDis[n.v]));
}
}
}
pq.add(new Node(food, 0));
while (!pq.isEmpty()) {
Node cur = pq.poll();
if (foodDis[cur.v] < cur.dis)
continue;
for (Node n : graph[cur.v]) {
if (foodDis[n.v] > foodDis[cur.v] + n.dis) {
foodDis[n.v] = foodDis[cur.v] + n.dis;
pq.add(new Node(n.v, foodDis[n.v]));
}
}
}
int answer = 0;
for (Integer person : people) {
if (kistDis[person] == Integer.MAX_VALUE) {
answer += -1;
} else
answer += kistDis[person];
if (foodDis[person] == Integer.MAX_VALUE) {
answer += -1;
} else
answer += foodDis[person];
}
System.out.println(answer);
bw.flush();
bw.close();
br.close();
}
}
문제를 해결하면서 하나의 문제가 있었는데, 인접리스트를 초기화 할때 나는 Arrays.fill을 써주었다. 이렇게 하니 모든 배열의 element에서 하나의 ArrayList를 공유하는 문제가 발생하였다. Arrays.fill을 쓸 때 collection 값을 넣지 않도록 주의해야겠다.
또한 기본적인 다익스트라 문제이므로 잘 평소에도 잘 이해하는 것이 중요할 것 같다.