백준 13141번: Ignition (Java)

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

13141번: Ignition

문제

 

서훈이는 오늘 있었던 알고리즘 과목 기말고사를 망쳐서 기분이 좋지 않다. 서훈이는 스트레스도 풀 겸 시험 문제로 나온 그래프를 불로 태우려고 한다.

서훈이는 그래프의 정점 (위 그림에서 동그라미로 표시된 곳) 중 한 곳에 불을 붙일 수 있다. 정점에 불이 붙으면 곧바로 노드와 연결된 간선을 따라서 불이 전달된다. 간선 위에서는 불은 1초당 1만큼의 거리를 이동한다. 만약 어떤 간선의 양 끝 정점에 불이 붙은 경우 불은 간선의 중앙까지 태운 후 꺼진다.

서훈이는 그래프를 최대한 빠른 시간 안에 전부 태우고 싶어한다. 서훈이를 도와 어떤 정점에 불을 붙일지 구하는 프로그램을 작성하여라. 단, 위 그림에서 간선끼리 교차하는 것은 무시한다.

입력

첫 번째 줄에는 그래프의 정점의 수 N과 간선의 수 M이 주어진다. (2 ≤ N ≤ 200, N-1 ≤ M ≤ 20,000)

두 번째 줄부터 M개의 줄에는 각 간선의 시작점 S, 끝점 E, 길이 L이 주어진다. (1 ≤ L ≤ 100)

시작점과 끝점이 같은 간선도 있을 수 있으며, 특정 두 정점을 직접 연결하는 간선의 수가 여러 개일 수 있다. 또한, 그래프의 모든 정점들은 간선들을 통해서 연결되어 있다.

출력

주어진 그래프를 모두 태우는 데 걸리는 최소 시간을 출력한다. 답은 소수점 아래 한 자리까지 출력한다. 문제의 특성 상 오차가 생길 일이 없으므로 출력 데이터와 정확히 일치해야 정답으로 처리한다.

 

---

 

일단 플로이드 문제집에서 접한 문제였기 때문에, 플로이드-와셜을 써야한다는 거 까지는 알았다. 이후 다익스트라까지 생각은 했는데, 선분이 타들어가는걸 시간 단위로 구현해야하나? 싶어서 하다가 포기했다. 다익스트라도 맞았는데...

 

풀이

두 정점을 잇는 간선이 2개 이상일 수 있다. 이 중 가장 작은 값만 받아들인 후, 플로이드-와셜을 수행한다. 그러면, 모든 두 점 사이의 최소 거리가 구해졌다. 이후, 1번째 점부터 N번째 점까지 다익스트라를 수행한다. i번째 다익스트라에 대해, 어떤 간선 e가 다 타는 시점은 ((점 i에서 e의 시작점까지 도달하는 최단 거리) + (점 i에서 e의 끝점까지 도달하는 최단 거리) + (e의 길이)) / 2가 된다. 따라서, i번째 점에서 다익스트라를 할 때 소요되는 시간은 max(e가 타는 시간)이며, 정답은 min(i번째 다익스트라에서의 max(e가 타는 시간)이다.

'플로이드 + 다익스트라를 N번 쓴다 + 타들어가는 시점은 시작점, 끝점 도달 시간으로 구하기'라는, 여러 기본적인 아이디어들이 잘 합쳐진 문제인 듯하다.

 

코드

import java.io.*;
import java.util.*;
 
public class Main {
 
    static final int INF = 1_000_000_007;
    static int[][] map;
    static int N, M;
    static long[] d;
    static List<List<Edge>> graph;
    static List<Edge> edges;
    
    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());
        
        map = new int[N+1][N+1];
        graph = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<Edge>());
            Arrays.fill(map[i], INF);
        }
        edges = new ArrayList<>();
        
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int S = Integer.parseInt(st.nextToken());
            int E = Integer.parseInt(st.nextToken());
            int L = Integer.parseInt(st.nextToken());
            edges.add(new Edge(S, E, L));
            graph.get(S).add(new Edge(S, E, L));
            graph.get(E).add(new Edge(E, S, L));
            map[S][E] = Math.min(map[S][E], L);
            map[E][S] = Math.min(map[E][S], L);
        }
        
        floyd(map);
        double ans = INF;
        for (int i = 1; i <= N; i++) {
            dijkstra(i);
            double temp = calc();
            ans = Math.min(ans, temp);
        }
        System.out.println(ans);
    }
 
    static class Edge implements Comparable<Edge> {
        int from;
        int to;
        long dist;
 
        public Edge(int from, int to, long dist) {
            this.from = from;
            this.to = to;
            this.dist = dist;
        }
 
        public int compareTo(Edge o) {
            return Long.compare(this.dist, o.dist);
        }
    }
    
    static void floyd(int[][] dist) {
        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
    
    static void dijkstra(int start) {
        d = new long[N+1];
        Arrays.fill(d, INF);
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        pq.offer(new Edge(0, start, 0));
        d[start] = 0;
        while (!pq.isEmpty()) {
            Edge cur = pq.poll();
            if (d[cur.to] < cur.dist) continue;
            for (Edge nxt: graph.get(cur.to)) {
                if (d[nxt.to] > cur.dist + nxt.dist) {
                    d[nxt.to] = cur.dist + nxt.dist;
                    pq.offer(new Edge(cur.to, nxt.to, cur.dist + nxt.dist));
                }
            }
        }
    }
    
    static double calc() {
        double ret = 0;
        for (Edge e: edges) {
            double temp = ((double) (e.dist + d[e.from] + d[e.to]) / 2);
            if (ret < temp) ret = temp;
        }
        return ret;
    }
}
 

 

---

 

여담

https://www.youtube.com/watch?v=KFv3D_S1PgU 

6월 30일부터 'Ignition' 이벤트 실시! 250레벨까지 1+2레벨업 하이퍼버닝 캐릭터 생성가능!