백준 2325 (개코전쟁) - java

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

2325번: 개코전쟁

 

문제

“앙두레 강”이 개미와 코끼리 결혼식에서 기차를 아름답게 만드는 것을 실패했기 때문에 식장이 아수라장이 되고 결혼이 물거품이 되어버렸다. 급기야는 왕국 간에 분쟁으로 이어져 개미왕국은 코끼리왕국을 공격하기로 결정하였다. 동물나라 지도에서 개미왕국은 1번 정점에 위치해 있고 코끼리왕국은 N번 정점에 위치해 있다. 따라서 개미왕국이 1번 정점에서 N번 정점으로 공격을 하러 가는 상황이다. (개미왕국은 최단거리로 이동을 하게 되고, 코끼리왕국은 움직이지 않는다)

“개미”와 “코끼리”의 앞 글자를 따서 이 전쟁은 “개코전쟁”으로 역사에 기억된다.

“앙두레 강”은 자신 때문에 발생한 이 전쟁을 어떻게든 막으려고 한다. 협상을 할 시간을 벌기 위해 개미왕국이 코끼리왕국에 도착하는 시간을 최대한 늦추려고 한다. 그래서 “앙두레 강”은 사자왕국의 도움을 빌어 도로 중 딱 하나를 파괴하려고 하는데 어느 도로를 파괴해야 개미왕국이 최단거리로 가더라도 그 거리를 최대로 할 수 있을까?

“앙두레 강”를 도와 1번 정점에서 N번 정점으로의 최단거리가 최대가 되도록 도로 하나를 파괴하도록 하자. (어떤 하나의 도로를 파괴하더라도 1번 정점에서 N번 정점으로 도달 가능하다)

 

유형 : 다익스트라 알고리즘 + 최적화 + 경로

 

접근 방식

• 간단하게 생각하자 !
  • 주어진 모든 간선을 한 개씩 check해봐야 할까?
    • NO!!!!!! : 최단 거리에 속하지 않은 간선을 금지시켜도 결과는 이전에 구한 최단 거리이다 !
    • 결국 최단 거리에 속하는 간선을 금지시키고 수행해야 한다.
  • 우선 최단 거리를 구하면서 경로를 구해야 한다.
    • 경로를 구하는 방법은 간단한데 path[] 배열을 사용하여 이전 정점을 기입하여 총 경로를 구한다.
  • 목적지부터 역순으로 탐색하여 간선 한 개씩 금지시키고 다익스트라 알고리즘을 수행하여 결과(최댓값)을 구한다.

 

전체 코드

import java.util.*;
import java.io.*;
public class Main {

    static int n = 0;
    static int m = 0;

    static ArrayList<Node>[] graph;

    static int[] pathList;

    static int result = 0;

    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        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(bf.readLine(), " ");
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            graph[v1].add(new Node(v2,c,i));
            graph[v2].add(new Node(v1,c,i));
        }

        first();

        int start = n;

        while(start != 0){

            result(start,pathList[start]);

            start = pathList[start];

            if(start == 0)
                break;
        }

        System.out.println(result);
        bf.close();
    }
    // 첫 번째 최단 경로 찾기
    static void first(){
        PriorityQueue<Node> pq = new PriorityQueue<>(
                (x,y) -> x.c - y.c
        );

        int[] path = new int[n+1];
        int[] dis = new int[n+1];

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

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

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

            if(cur.v == n){
                break;
            }

            for(Node next : graph[cur.v]){

                if(dis[next.v] > dis[cur.v] + next.c){
                    dis[next.v] = dis[cur.v] + next.c;
                    path[next.v] = cur.v;
                    pq.add(new Node(next.v,dis[next.v],next.num));
                }
            }
        }

        pathList = path;
    }
    // 간선 한 개를 BAN 할 때 최단 거리
    static void result(int cx,int cy){


        PriorityQueue<Node> pq = new PriorityQueue<>(
                (x,y) -> x.c - y.c
        );

        int[] dis = new int[n+1];

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

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

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

            if(cur.v == n){
                break;
            }

            for(Node next : graph[cur.v]){
                // 금지된 간선의 경우 지나친다
                if((cur.v == cx && next.v == cy) || (cur.v == cy && next.v == cx))
                    continue;

                if(dis[next.v] > dis[cur.v] + next.c){
                    dis[next.v] = dis[cur.v] + next.c;
                    pq.add(new Node(next.v,dis[next.v],next.num));
                }
            }
        }

        result = Math.max(result,dis[n]);

    }
}
class Node{
    int v;
    int c;

    int num;

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