[BaekJoon] 13911 집 구하기 (Java)

1.  문제 링크

https://www.acmicpc.net/problem/13911

2.  문제

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int V, E, x, y;
    static int[] mcDonaldDistance, starbucksDistance, vertexType; // 각 정점의 맥도날드까지의 거리, 각 정점의 스타벅스까지의 거리, 정점 종류(-1 : 맥도날드, 1 : 스타벅스, 0 : 집)
    static Map<Integer, List<Edge>> edges; // 위치들 사이의 간선 정보
    static boolean[] visited; // 각 위치를 방문하였는지에 대한 배열
    static List<Integer> mcDonald, starbucks; // 맥도날드, 스타벅스에 해당하는 위치들

    static void input() {
        Reader scanner = new Reader();

        V = scanner.nextInt();
        E = scanner.nextInt();

        edges = new HashMap<>();
        mcDonaldDistance = new int[V + 1];
        starbucksDistance = new int[V + 1];
        vertexType = new int[V + 1];
        visited = new boolean[V + 1];
        for(int vertex = 1; vertex <= V; vertex++) {
            edges.put(vertex, new ArrayList<>());
            mcDonaldDistance[vertex] = Integer.MAX_VALUE;
            starbucksDistance[vertex] = Integer.MAX_VALUE;
        }

        for(int edge = 0; edge < E; edge++) {
            int vertex1 = scanner.nextInt(), vertex2 = scanner.nextInt(), weight = scanner.nextInt();
            edges.get(vertex1).add(new Edge(vertex2, weight));
            edges.get(vertex2).add(new Edge(vertex1, weight));
        }

        int mcNum = scanner.nextInt();
        x = scanner.nextInt();
        mcDonald = new ArrayList<>();

        for(int idx = 0; idx < mcNum; idx++) {
            int vertex = scanner.nextInt();
            mcDonald.add(vertex);
            vertexType[vertex] = -1;
        }

        int starNum = scanner.nextInt();
        y = scanner.nextInt();
        starbucks = new ArrayList<>();
        for(int idx = 0; idx < starNum; idx++) {
            int vertex = scanner.nextInt();
            starbucks.add(vertex);
            vertexType[vertex] = 1;
        }
    }

    static void solution() {
        calcMcDonaldDistance();
        calcStarbucksDistance();

        System.out.println(getMinDistance());
    }

    static int getMinDistance() {
        int min = Integer.MAX_VALUE;

        // 스타벅스까지의 최소 거리 + 맥도날드까지의 최소 거리 중 최소값을 구한다
        for(int vertex = 1; vertex <= V; vertex++) {
            if(vertexType[vertex] != 0) continue;
            if(mcDonaldDistance[vertex] == Integer.MAX_VALUE || starbucksDistance[vertex] == Integer.MAX_VALUE)
                continue;

            min = Math.min(min, mcDonaldDistance[vertex] + starbucksDistance[vertex]);
        }

        // min값이 한 번도 갱신되지 않았다면 문제의 조건에 맞는 곳이 없다는 것이므로 -1을 반환한다
        if(min == Integer.MAX_VALUE) return -1;
        else return min;
    }

    // 각 지점이 스타벅스로부터 떨어진 최소 거리를 구한다
    static void calcStarbucksDistance() {
        PriorityQueue<Edge> queue = new PriorityQueue<>();
        for(int idx = 0; idx < starbucks.size(); idx++) {
            int starbucksVertex = starbucks.get(idx);
            if(visited[starbucksVertex]) continue; // 이미 방문한 적 있는 스타벅스 위치라면 해당 정점은 체크하지 않는다

            visited[starbucksVertex] = true;
            queue.offer(new Edge(starbucksVertex, 0));

            // 다익스트라
            while(!queue.isEmpty()) {
                Edge cur = queue.poll();
                int curVertex = cur.vertex, curDistance = cur.distance;
                for(int idx2 = 0; idx2 < edges.get(curVertex).size(); idx2++) {
                    int nextVertex = edges.get(curVertex).get(idx2).vertex;
                    int nextDistance = edges.get(curVertex).get(idx2).distance;

                    // 다음 목적지가 스타벅스이고 아직 방문한 적이 없다면
                    // 방문 체크를 하고 해당 위치가 스타벅스이니 스타벅스까지의 거리를 0으로 하며 다음 탐색을 위해 PriorityQueue에 집어넣는다
                    if(vertexType[nextVertex] == 1 && !visited[nextVertex]) {
                        visited[nextVertex] = true;
                        starbucksDistance[nextVertex] = 0;
                        queue.offer(new Edge(nextVertex, 0));
                    } else { // 그렇지 않다면(목적지가 스타벅스가 아니거나 이미 방문한 곳이라면)
                        // 다음 목적지까지의 거리가 y가 넘는지 확인한다
                        // 넘는다면 최단거리가 y 이하여야 한다는 문제의 조건과 맞지 않으므로 다음 케이스를 확인한다
                        if(nextDistance + curDistance > y) continue;
                        // 이미 구해놓은 다음 목적지까지 가는 데에 필요한 최소 거리보다 지금 경로로 다음 목적지까지 가는 거리가 더 크다면
                        // 최소가 될 수 없으므로 다음 케이스를 확인한다
                        if(starbucksDistance[nextVertex] < nextDistance + curDistance) continue;

                        // 다음 목적지까지의 최소 거리를 갱신하고 다음 탐색을 위해 PriorityQueue에 넣는다
                        starbucksDistance[nextVertex] = nextDistance + curDistance;
                        queue.offer(new Edge(nextVertex, nextDistance + curDistance));
                    }
                }
            }
        }
    }

    // 스타벅스 거리를 구하는 것과 마찬가지로 맥도날드 거리도 구한다
    static void calcMcDonaldDistance() {
        PriorityQueue<Edge> queue = new PriorityQueue<>();

        for(int idx = 0; idx < mcDonald.size(); idx++) {
            int mcDonaldVertex = mcDonald.get(idx);
            if(visited[mcDonaldVertex]) continue;

            visited[mcDonaldVertex] = true;
            queue.offer(new Edge(mcDonaldVertex, 0));
            mcDonaldDistance[mcDonaldVertex] = 0;

            while(!queue.isEmpty()) {
                Edge cur = queue.poll();
                int curVertex = cur.vertex, curDistance = cur.distance;

                for(int idx2 = 0; idx2 < edges.get(curVertex).size(); idx2++) {
                    int nextVertex = edges.get(curVertex).get(idx2).vertex;
                    int nextDistance = edges.get(curVertex).get(idx2).distance;

                    if(vertexType[nextVertex] == -1 && !visited[nextVertex]) {
                        visited[nextVertex] = true;
                        mcDonaldDistance[nextVertex] = 0;
                        queue.offer(new Edge(nextVertex, 0));
                    } else {
                        if(nextDistance + curDistance > x) continue;
                        if(mcDonaldDistance[nextVertex] < nextDistance + curDistance) continue;

                        mcDonaldDistance[nextVertex] = nextDistance + curDistance;
                        queue.offer(new Edge(nextVertex, nextDistance + curDistance));
                    }
                }
            }
        }
    }

    static class Edge implements Comparable<Edge> {
        int vertex, distance;

        public Edge(int vertex, int distance) {
            this.vertex = vertex;
            this.distance = distance;
        }

        @Override
        public int compareTo(Edge o) {
            return distance - o.distance;
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}