백준 11952 (좀비) - java

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

11952번: 좀비

 

문제

JOI국은 N개의 도시와 M개의 도로로 이루어져 있다. 모든 도시는 도로로 연결되어 있으며, 각 도로를 통하지 않고는 다른 도시로 갈 수 없다.

이번에 K개의 도시는 좀비에 의해서 점령당했다. ㅠㅠ

따라서 경곽이는 벙커가 있는 가장 안전한 도시로 피난을 가기로 했다. 경곽이는 현재 1번 도시에 살고 있으며, 벙커가 있는 가장 안전한 피난처는 N번 도시이다. 1번 도시와 N번 도시는 아직 좀비에게 점령당하지 않았다.

경곽이는 각 도시를 이동할 때마다 1박을 해야하고, 1박을 할 때 숙박비를 지불해야 한다. 만약 그 도시가 좀비에게 점령당했다면 숙박이 불가능하다.

좀비에게 점령당한 도시로 부터 S번 이하의 이동으로 이동할 수 있는 모든 도시는 위험한 도시로 정의하며, 그 이외의 도시는 안전한 도시로 정의할 때, 만약 그 도시가 안전한 도시라면 숙박비가 p원이고, 만약 그 도시가 위험한 도시라면 숙박비는 q원이다. (좀비로부터 보호받기 위한 특별한 시큐리티 서비스를 제공하기 때문에 좀 더 비싸다 ㅠㅠ)

경곽이가 도시 1부터 N으로 이동하는 데 드는 최단 비용을 구하자.

 

유형 : BFS + 다익스트라

 

접근 방식

• 구현 측면에서 난이도가 있는 문제이다. 천천히 흐름을 잡아 보자
• 구해야 하는 것은 1 - N까지 이동하는데 드는 최단 비용이다. 
  • 다익스트라 알고리즘을 통해 최단 비용을 구하도록 하자
    • 주의해야 할 점은 입력의 크기가 상당히 크기 때문에 우선순위 큐를 사용하여 시간복잡도를 줄이는 것이다.
  • 좀비 위험 지역에 대한 판단
    • BFS를 통해 좀비에게 점령된 도시로부터 s 거리 안에 있는 지역을 구분해줘야 한다.
    • zombie[] 라는 배열을 만들고
      • 0 : 좀비 안전 지역 : 비용 p
      • 1 : 좀비 점령 지역 : 못감
      • 2 : 좀비 위험 지역 : 비용 q
• 좀비 위험 지역 판단 (danger 메소드) -> 탐색 (search 메소드)

 

전체 코드

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

public class Main {
    static int n = 0;
    static int m = 0;
    static int k = 0;
    static int s = 0;

    static int p = 0;
    static int q = 0;

    static int[] zombie;

    static ArrayList<Integer>[] graph;

    public static void main(String[] args) throws Exception {
        StringBuilder sb = new StringBuilder();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        s = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        p = Integer.parseInt(st.nextToken());
        q = Integer.parseInt(st.nextToken());

        zombie = new int[n+1];

        for(int i=1;i<=k;i++){
            int tmp = Integer.parseInt(br.readLine());
            zombie[tmp] = 1;
        }

        graph = new ArrayList[n+1];
        for(int i=1;i<=n;i++){
            graph[i] = new ArrayList<>();
        }

        for(int i=1;i<=m;i++){
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());


            graph[x].add(y);
            graph[y].add(x);
        }

        danger();



        search();

        br.close();
    }
    static void danger(){
        Queue<Integer> q = new LinkedList<>();
        int[] v = new int[n+1];

        for(int i=1;i<=n;i++){
            if(zombie[i] == 1){
                q.add(i);
                v[i] = 1;
            }
        }

        while(!q.isEmpty()){
            int cur = q.poll();

            if(v[cur] -1 >= s){
                continue;
            }


            for(int next : graph[cur]){
                if(v[next] == 0 || v[next] > v[cur] + 1){
                    v[next] = v[cur] + 1;
                    zombie[next] = 2;
                    q.add(next);
                }
            }
        }
    }
    static void search(){
        PriorityQueue<Node> pq = new PriorityQueue<>(
                (x,y) -> Long.compare(x.c,y.c)
        );
        boolean[] v = new boolean[n+1];
        long[] dis = new long[n+1];

        for(int i=1;i<=n;i++){
            dis[i] = Long.MAX_VALUE;
        }

        dis[1] = 0;

        pq.add(new Node(1,0));

        while(!pq.isEmpty()){
            Node cur = pq.poll();

            if(cur.v == n)
                continue;


            for(int next : graph[cur.v]){
                if(zombie[next] == 2){
                    if(dis[next] > dis[cur.v] + q){
                        dis[next] = dis[cur.v] + q;
                        pq.add(new Node(next,dis[next]));
                    }
                }else if(zombie[next] == 0){
                    if(dis[next] > dis[cur.v] + p){
                        dis[next] = dis[cur.v] + p;
                        pq.add(new Node(next,dis[next]));
                    }
                }
            }
        }

        if(zombie[n] == 0){
            dis[n] -= p;
        }else if(zombie[n] == 2){
            dis[n] -= q;
        }

        System.out.println(dis[n]);
    }
}
class Node{
    int v;
    long c;

    Node(int v,long c){
        this.v = v;
        this.c = c;
    }
}