[백준] 14221번 - 편의점 (java)

Baekjoon 14221 - 편의점

문제

영선이는 이사할 일이 생겨 집을 알아보고 있다. 영선이는 혼자 살기 때문에, 편의점에서 대충 때울 때가 많아, 집을 고르는 기준을 편의점과의 거리가 가장 가까운 곳으로 하려한다.

영선이가 이사할 도시는 정점과 간선으로 표현할 수 있는데, 이사가려 하는 집의 후보들과 편의점은 정점들 위에 있다.

영선이는 캠프 강사 준비로 바쁘므로, 대신하여 집을 골라주자. 만약 거리가 같은 지점이 여러 개라면 정점 번호가 가장 낮은 곳으로 골라주자.

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	512 MB	402	85	54	22.222%

입력

처음 줄에는 정점의 개수 n, 간선의 개수 m이 주어진다.(2 ≤ n ≤ 5,000, 1 ≤ m ≤ 100,000) 다음 m줄에는 a,b,c가 주어지는데 이는 a, b를 잇는 간선의 거리가 c라는 것이다.(1 ≤ a, b ≤ n, 1 ≤ c ≤ 10,000)

다음 줄에는 집의 후보지의 개수 p와 편의점의 개수 q가 주어진다.(2 ≤ p+q ≤ n, 1 ≤ p, 1 ≤ q) 다음 줄에는 집의 후보지들의 정점번호, 그 다음줄에는 편의점의 정점번호가 주어진다. 집의 후보지와 편의점은 서로 겹치지 않는다.

출력

편의점으로부터 가장 가까운 지점에 있는 집 후보의 정점 번호를 출력하시오. 만약 거리가 같은 곳이 여러 군데라면 정점 번호가 낮은 곳을 출력하시오.

풀이 (Dijkstra)

1. 모든 편의점을 시작 정점으로 하여 다익스트라 알고리즘을 수행한다
2. 다익스트라 수행 과정 중 현재 정점이 집이면 거리를 비교하고 정답을 반영한다.
3. 다익스트라가 끝나면 정답을 출력한다.

과정

• 다익스트라

static void dijkstra() {
    PriorityQueue<Edge> pq = new PriorityQueue<>();
    int[] distance = new int[N + 1];
    Arrays.fill(distance, Integer.MAX_VALUE);
    Arrays.fill(visited, false);

    for(int convenience : conv) {                // 모든 편의점을 시작 정점으로 한다.
        pq.offer(new Edge(convenience, 0));
        distance[convenience] = 0;
        visited[convenience] = true;
    }

    while (!pq.isEmpty()) {
        Edge curr = pq.poll();

        if (home.contains(curr.vertex)) {            // 현재 위치가 집일 경우
            if (minDist > distance[curr.vertex]) {        // 최단거리일 경우
                answer = curr.vertex;
                minDist = distance[curr.vertex];
            } else if (minDist == distance[curr.vertex]) {    // 최단거리와 거리가 같을 경우
                answer = Math.min(answer, curr.vertex);
            }
        }

        visited[curr.vertex] = true;

        for (Edge temp = adjList[curr.vertex]; temp != null; temp = temp.link) {
            if (!visited[temp.vertex] && distance[curr.vertex] + temp.weight < distance[temp.vertex]) {
                pq.offer(new Edge(temp.vertex, distance[curr.vertex] + temp.weight));
                distance[temp.vertex] = distance[curr.vertex] + temp.weight;
            }
        }
    }
}

최종 소스코드

package BJ_Practice.Gold;

import java.io.*;
import java.util.*;

public class BJ_G4_14221_편의점 {
    static int N, M, P, Q;
    static int minDist = Integer.MAX_VALUE, answer = 10000;
    static boolean[] visited;
    static Edge[] adjList;
    static Set<Integer> home = new HashSet<>();
    static Set<Integer> conv = new HashSet<>();

    static class Edge implements Comparable<Edge> {
        int vertex;
        int weight;
        Edge link;

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

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

        @Override
        public int compareTo(Edge o) {
            if (this.weight == o.weight)
                return Integer.compare(this.vertex, o.vertex);
            return Integer.compare(this.weight, o.weight);
        }
    }

    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());

        adjList = new Edge[N + 1];
        visited = new boolean[N + 1];
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());

            adjList[start] = new Edge(end, weight, adjList[start]);
            adjList[end] = new Edge(start, weight, adjList[end]);
        }

        st = new StringTokenizer(br.readLine());
        P = Integer.parseInt(st.nextToken());
        Q = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < P; i++) {
            home.add(Integer.parseInt(st.nextToken()));
        }

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < Q; i++) {
            conv.add(Integer.parseInt(st.nextToken()));
        }
        // --------------------------------------------- 입력 끝

        dijkstra();

        System.out.println(answer);

    }

    static void dijkstra() {
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        int[] distance = new int[N + 1];
        Arrays.fill(distance, Integer.MAX_VALUE);
        Arrays.fill(visited, false);

        for(int convenience : conv) {                // 모든 편의점을 시작 정점으로 한다.
            pq.offer(new Edge(convenience, 0));
            distance[convenience] = 0;
            visited[convenience] = true;
        }

        while (!pq.isEmpty()) {
            Edge curr = pq.poll();

            if (home.contains(curr.vertex)) {            // 현재 위치가 집일 경우
                if (minDist > distance[curr.vertex]) {        // 최단거리일 경우
                    answer = curr.vertex;
                    minDist = distance[curr.vertex];
                } else if (minDist == distance[curr.vertex]) {    // 최단거리와 거리가 같을 경우
                    answer = Math.min(answer, curr.vertex);
                }
            }

            visited[curr.vertex] = true;

            for (Edge temp = adjList[curr.vertex]; temp != null; temp = temp.link) {
                if (!visited[temp.vertex] && distance[curr.vertex] + temp.weight < distance[temp.vertex]) {
                    pq.offer(new Edge(temp.vertex, distance[curr.vertex] + temp.weight));
                    distance[temp.vertex] = distance[curr.vertex] + temp.weight;
                }
            }
        }
    }
}