BOJ#13911 집 구하기

BOJ#13911 집 구하기

* 문제

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

University > 서강대학교 > 제 12회 총장배 서강대학교 프로그래밍 대회 Master F번

* 풀이

매우 매우 추천하는 문제입니다.

- 처음 생각한 알고리즘

1. 맥도날드 지점별로 다익스트라

2. 스타벅스 지점별로 다익스트라

3. 조건 만족하는 것 찾아내기

문제를 본격적으로 풀어보려는데,, 뭔가 찜찜합니다.

입력값 범위가 심상치 않아 문제를 풀기전에 시간복잡도를 계산해봅니다.

V ≤ 10,000, E ≤ 300,000

맥도날드 다익스트라 (V-2)번 : O(E*log(V)) * V-2번

스타벅스 다익스트라 (V-2)번 : O(E*log(V)) * V-2번

조건 만족하는 것 찾아내기 : ??

결론 : 시간 복잡도 폭발 -> 단순하게 다익스트라 돌리면 안됨.

(아무튼 문제에 0이 많이 보이면 조심해야합니다 😂)

- 다시 생각한 알고리즘

다익스트라를 (V-2)*2번 돌릴 수는 없다. (V ≤ 10,000) 

맥도날드와 각 집의 최단거리, 스타벅스와 각 집의 최단거리를 한방에 구할 수 없을까?

1. 더미 노드를 하나 만들고 맥도날드 노드들과 cost 0으로 연결해줍니다. 즉, 맥도날드 부모 노드를 1개 만듭니다.

2. 더미 노드를 하나 만들고 스타벅스 노드들과 cost 0으로 연결해줍니다. 즉, 스타벅스 부모 노드를 1개 만듭니다.

3. 맥도날드 부모 더미 노드에서 다익스트라 돌립니다. 그러면 맥도날드에서 각각의 집까지 최단거리를 구할 수 있습니다.

4. 스타벅스 부모 더미 노드에서 다익스트라 돌립니다. 그러면 스타벅스에서 각각의 집까지 최단거리를 구할 수 있습니다.

5. 그러면 최단 거리 배열(dist)이 2개가 나옵니다.

6. 문제 조건에 맞게 답을 구합니다.

끝.

☞ 관련 문제 :

5214번 - 환승 (하이퍼튜브 문제) https://www.acmicpc.net/problem/5214

- 개인적으로 실수한 점

1. 그래프 간선 입력받을 때, 단방향인지 양방향인지 문제 잘 볼 것

2. 다익스트라 - 현재 노드에서 연결된 간선들만 조사하자

3. 문제 조건에 따라 마지막 dist 2차원 배열 조사할 때, 불필요한 loop 추가했던 것

-> 다음에는 

static int[][] dist = new int[2][10100]; 이 아니라

static int[][] dist = new int[10100][2]; 로 선언하면 헷갈리지 않을 듯 하다.

4. "만일 원하는 집이 존재하지 않으면 -1을 출력한다."

-> 난 왜 0을 출력하고 있었던 것인가.. 1시간 날림..😃

---

* 나의 코드

https://github.com/stack07142/BOJ/blob/96e3fa23fed287ea348fa687e8842e84ddabbf1e/BOJ%2313911_GetHouse/src/Main.java

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

/**
 * BOJ#13911 집 구하기
 * https://www.acmicpc.net/problem/13911
 */

public class Main {

    static final int INF = 100000000;
    static final int MCDONALDS = 0;
    static final int STARBUCKS = 1;

    static int nV, nE;
    static int M; // 맥세권
    static int S; // 스세권
    static int[] limit = new int[2];
    static ArrayList<ArrayList<Edge>> adjList = new ArrayList<ArrayList<Edge>>();
    static int[][] dist = new int[2][10100];

    static {

        for (int i = 0; i < 2; i++) {

            Arrays.fill(dist[i], INF);
        }
    }

    public static void main(String[] args) throws IOException {

        // 집이 아닌 것들의 모음(맥도날드, 스타벅스)
        HashSet<Integer> notHouse = new HashSet<Integer>();

        // input - edge
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        nV = Integer.parseInt(st.nextToken());
        nE = Integer.parseInt(st.nextToken());

        // 1부터 ~ nV까지 + 더미노드 2개 = 1부터 nV+2까지
        for (int i = 0; i < nV + 3; i++) {

            adjList.add(new ArrayList<Edge>());
        }

        for (int i = 0; i < nE; i++) {

            st = new StringTokenizer(br.readLine());

            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            adjList.get(u).add(new Edge(v, w));
            adjList.get(v).add(new Edge(u, w));
        }

        // input - mcdonals
        st = new StringTokenizer(br.readLine());

        M = Integer.parseInt(st.nextToken());
        limit[MCDONALDS] = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {

            int src = Integer.parseInt(st.nextToken());

            notHouse.add(src);

            // 모든 맥도날드의 부모 더미노드 1개 생성 후 weight 0으로 연결해준다
            adjList.get(nV + 1).add(new Edge(src, 0));
        }

        // input - starbucks
        st = new StringTokenizer(br.readLine());

        S = Integer.parseInt(st.nextToken());
        limit[STARBUCKS] = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < S; i++) {

            int src = Integer.parseInt(st.nextToken());

            notHouse.add(src);

            // 모든 스타벅스의 부모 더미노드 1개 생성 후 weight 0으로 연결해준다
            adjList.get(nV + 2).add(new Edge(src, 0));
        }

        // solve - dijkstra
        dijkstra(nV + 1, MCDONALDS);
        dijkstra(nV + 2, STARBUCKS);

        // solve - condition check
        int minCost = INF;

        // 실수했던 부분 #1 : 2차원 배열 조사 x, nV만큼만 조사하면 된다.
        for (int i = 1; i <= nV; i++) {

            if (notHouse.contains(i)) continue;
            if (dist[MCDONALDS][i] <= limit[MCDONALDS] &&
                    dist[STARBUCKS][i] <= limit[STARBUCKS]) {

                minCost = Math.min(minCost, dist[MCDONALDS][i] + dist[STARBUCKS][i]);
            }
        }

        System.out.println(minCost >= INF ? -1 : minCost);
    } // ~ main

    static void dijkstra(int src, int idx) {

        PriorityQueue<Node> pq = new PriorityQueue<Node>();

        pq.add(new Node(src, 0));
        dist[idx][src] = 0;

        while (!pq.isEmpty()) {

            Node u = pq.poll();

            if (dist[idx][u.node] < u.dist) continue;

            // 실수했던 부분 #2 : u.node(현재노드)에 연결된 간선들만 조사
            ArrayList<Edge> list = adjList.get(u.node);
            for (Edge e : list) {

                if (dist[idx][e.toNode] > dist[idx][u.node] + e.weight) {

                    dist[idx][e.toNode] = dist[idx][u.node] + e.weight;
                    pq.add(new Node(e.toNode, dist[idx][e.toNode]));
                }
            }
        } // ~while loop
    } // ~ dijkstra

}

class Edge {

    int toNode;
    int weight;

    Edge(int toNode, int weight) {

        this.toNode = toNode;
        this.weight = weight;
    }
}

class Node implements Comparable<Node> {

    int node;
    int dist;

    Node(int node, int dist) {

        this.node = node;
        this.dist = dist;
    }

    @Override
    public int compareTo(Node o) {

        return this.dist < o.dist ? -1 : 1;
    }
}