백준 12834 JAVA : 주간 미팅

문제

백준 문제 링크 : https://www.acmicpc.net/problem/12834

풀이전략

  1. 팀에서 원하는 회의 장소를 구하는 문제이다. 단 이 문제는 거꾸로 KIST, 씨알푸드의 위치에서 다른 정점으로 까지의 최소값을 구하고, 이를 다 더하면 결국 각 사람들의 위치에서 KIST, 씨알푸드의 위치로의 최소값을 구하는 것이다.
  2. 한 정점에서 다른 정점으로의 최소값을 구하는 문제이므로 다익스트라 알고리즘을 사용하면 된다.
  3. 다익스트라 알고리즘의 시간복잡도는 O(ElogV)이다. 이 문제에서 V <= 1000, E <=10000이므로 다익스트라 알고리즘을 2번 (KIST, 씨알푸드) 돌려도 시간은 충분하므로 문제를 해결 할 수 있다.

코드

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 값을 넣지 않도록 주의해야겠다.

또한 기본적인 다익스트라 문제이므로 잘 평소에도 잘 이해하는 것이 중요할 것 같다.


Written by@Gomster
항상 노력하고 나아가는 백엔드 개발자가 되고 싶은 대학생입니다.

GitHub