백준 28019 (산지니의 여행계획) - java

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

 

문제

산지니가 여행 계획을 짜려고 한다.

렌터카 서비스를 이용하여 𝑁개의 도시를 모두 방문할 계획인 산지니는 지도에서 가려고 하는 도시 간의 직통 도로들을 살펴본다.

운전대를 잡아야 하는 산지니는 기억력이 좋지 않아 최대한 직통 도로를 적게 선택하면서도, 여러 풍경을 차 안에서 느긋이 즐기고 싶기에 선택한 도로 길이의 합이 최대가 되기를 원한다.

산지니와 같이 여행하게 된 당신은 산지니의 의견을 반영하여 이용할 도로를 선택하고, 그 도로를 토대로 이동 경로를 대신 짜주려 한다.

모든 도시에는 이용하고자 하는 렌터카 서비스가 있어, 마지막 도시를 방문하면 시작 도시로 돌아가지 않고 그 도시에서 차량을 반납하기로 하였다.

여행을 시작할 도시는 산지니가 정해두었다. 최적의 경로를 구하여 운전 거리를 최대한 줄여보자.

 

유형 : MST + 그래프 탐색

 

접근 방식

 

1. '최대한 직통 도로를 적게 선택하면서도, 여러 풍경을 차 안에서 느긋이 즐기고 싶기에 선택한 도로 길이의 합이 최대가 되기를 원한다.'

• 그래프 이론에 대한 이해를 가지고 응용을 해서 풀어야 하는 문제이다.
• 우선 '최대한 직통 도로를 적게 선택하면서도, 여러 풍경을 차 안에서 느긋이 즐기고 싶기에 선택한 도로 길이의 합이 최대가 되기를 원한다.' 의 의미를 이해해야 한다.
• 우선 모든 도시를 방문하면서 선택하는 도로의 개수가 가장 적기 위해서는 그래프를 트리 구조로 만들어야 한다.
  • 그리고 간선에 가중치가 있기 때문에 MST 문제이다.
  • 하지만 문제에서 도로 길이의 합이 최대가 되길 원한다. -> 이를 MST 구조로 해결하기 위해 나는 모든 간선의 가중치에 -1을 곱하고 MST를 구했다.

2. 마지막 도시를 방문하면 시작 도시로 돌아가지 않고 그 도시에서 차량을 반납하기로 하였다.

• 즉 2번 지나치는 간선이 몇개 존재한다는 것이다. 가장 길이가 짧게 마지막 도시까지 가는 방법은 간단하다.
  • 찢어지는 경로 중에 가장 길이가 긴 경로를 1번만 건너는 것이다.
• MST를 구하면서 사용된 간선을 바탕으로 그래프(트리)를 만든다.
  • 시작점을 기준으로 BFS를 수행한다.
  • 더 이상 진행이 불가능한 경우 해당 경로의 값을 바탕으로 최장 경로를 구한다.
• 모든 간선 *2  - (최장 경로) 가 정답이다.

전체 코드

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

public class Main {

    static int n,m,s;

    static int[] root;

    static boolean[] v;

    static ArrayList<int[]>[] graph;

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

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

        root = new int[n+1];
        graph = new ArrayList[n+1];
        v = new boolean[n+1];

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

        long result = 0l;

        PriorityQueue<int[]> pq = new PriorityQueue<>(
                (x,y) -> x[2] - y[2]
        );

        for(int i = 1 ; i <= m ; i++){
            st = new StringTokenizer(br.readLine()," ");

            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken()) * -1;

            pq.add(new int[]{v1,v2,c});
        }

        st = new StringTokenizer(br.readLine()," ");
        s = Integer.parseInt(st.nextToken());

        int count = 0;

        while(!pq.isEmpty()){
            int[] cur = pq.poll();

            if(find(cur[0]) != find(cur[1])){
                union(cur[0],cur[1]);
                count += 1;

                result += 2 * (cur[2] * -1);

                graph[cur[0]].add(new int[]{cur[1],cur[2] * -1});
                graph[cur[1]].add(new int[]{cur[0],cur[2] * -1});
            }

            if(count == n - 1)
                break;
        }

        long tmpResult = bfs();

        System.out.println(result - tmpResult);

        br.close();
    }

    static long bfs(){
        long result = 0;
        Queue<Node> q = new ArrayDeque<>();
        q.add(new Node(s,0));
        v[s] = true;

        while(!q.isEmpty()){
            Node cur = q.poll();
            boolean find = true;

            for(int[] next : graph[cur.v]){
                if(!v[next[0]]){
                    v[next[0]] = true;
                    find = false;
                    q.add(new Node(next[0],cur.c + next[1]));
                }
            }

            if(find){
                result = Math.max(result,cur.c);
            }
        }

        return result;
    }

    static int find(int x){
        if(x == root[x])
            return root[x];

        return root[x] = find(root[x]);
    }

    static void union(int x,int y){
        x = find(x);
        y = find(y);

        if(x < y){
            root[y] = x;
        }else{
            root[x] = y;
        }
    }

    static class Node{
        int v;
        long c;

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