12월 12일 - 빌라봉[BOJ/8872]

문제 설명

• 𝑁개의 빌라봉과 𝑀개의 이미 존재하는 양방향 길이 주어진다.
• 모든 빌라봉이 연결될 수 있도록
• 𝑁−𝑀−1개의 새로운 길을 추가해야 한다. 새로 추가된 길을 통행하는 데 걸리는 시간은 항상 𝐿이다.
• 모든 빌라봉 쌍 사이의 최대 통행 시간이 최소가 되도록 해야 한다.
• 목표는 최적의 길 추가 방식을 찾아 최소의 최대 통행 시간을 계산하는 것이다.

코드

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

public class Main {
    static int N, M, L, ans = Integer.MIN_VALUE;
    static List<List<int[]>> adj = new ArrayList<>();
    static boolean[] isVisited;
    static List<Integer> currentTree = new ArrayList<>();
    static List<Integer> radiusList = new ArrayList<>();
    static int v1, dist1, v2, dist2;
    static Map<Integer, int[]> parent = new HashMap<>();

    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());
        L = Integer.parseInt(st.nextToken());

        for (int i = 0; i < N; i++) {
            adj.add(new ArrayList<>());
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            int T = Integer.parseInt(st.nextToken());
            adj.get(A).add(new int[]{B, T});
            adj.get(B).add(new int[]{A, T});
        }

        isVisited = new boolean[N];
        for (int i = 0; i < N; i++) {
            if (!isVisited[i]) {
                findRadius(i);
            }
        }

        Collections.sort(radiusList, Collections.reverseOrder());

        if (radiusList.size() >= 2 && radiusList.get(0) + radiusList.get(1) + L >= ans) {
            ans = radiusList.get(0) + radiusList.get(1) + L;
        }
        if (radiusList.size() >= 3 && radiusList.get(1) + radiusList.get(2) + 2 * L >= ans) {
            ans = radiusList.get(1) + radiusList.get(2) + 2 * L;
        }

        System.out.println(ans);
    }

    static void findRadius(int root) {
        currentTree.clear();
        dist1 = Integer.MIN_VALUE;
        dist2 = Integer.MIN_VALUE;

        dfs1(root, 0);

        for (int node : currentTree) {
            isVisited[node] = false;
        }

        dfs2(v1, 0);

        int radius = Integer.MAX_VALUE;
        int curDist = 0;
        int v = v2;

        if (dist2 > ans) {
            ans = dist2;
        }

        if (dist2 == 0) {
            radiusList.add(0);
            return;
        }

        while (v != v1) {
            radius = Math.min(radius, Math.max(curDist, dist2 - curDist));
            curDist += parent.get(v)[1];
            v = parent.get(v)[0];
        }

        radiusList.add(radius);
    }

    static void dfs1(int cur, int dist) {
        currentTree.add(cur);
        isVisited[cur] = true;

        if (dist > dist1) {
            v1 = cur;
            dist1 = dist;
        }

        for (int[] next : adj.get(cur)) {
            if (isVisited[next[0]]) continue;
            dfs1(next[0], dist + next[1]);
        }
    }

    static void dfs2(int cur, int dist) {
        currentTree.add(cur);
        isVisited[cur] = true;

        if (dist > dist2) {
            v2 = cur;
            dist2 = dist;
        }

        for (int[] next : adj.get(cur)) {
            if (isVisited[next[0]]) continue;
            parent.put(next[0], new int[]{cur, next[1]});
            dfs2(next[0], dist + next[1]);
        }
    }
}

코드 설명

1. 입력 및 초기화

• adj는 각 빌라봉의 인접 리스트를 저장하며, 각 도로는 [연결 빌라봉, 통행 시간] 형식으로 저장된다.
• radiusList는 각각의 독립된 트리의 반지름을 저장한다.
• isVisited는 DFS 방문 여부를 확인하기 위한 배열이다.

2. 독립된 트리의 반지름 계산

static void findRadius(int root) {
    currentTree.clear();
    dist1 = Integer.MIN_VALUE;
    dist2 = Integer.MIN_VALUE;

    dfs1(root, 0); // 첫 번째 DFS로 가장 먼 노드 v1을 찾음

    for (int node : currentTree) {
        isVisited[node] = false;
    }

    dfs2(v1, 0); // 두 번째 DFS로 v1에서 가장 먼 노드 v2를 찾음

    // v1과 v2를 잇는 경로의 중심에서 최대-최소 거리 계산
    int radius = Integer.MAX_VALUE;
    int curDist = 0;
    int v = v2;

    if (dist2 > ans) {
        ans = dist2;
    }

    if (dist2 == 0) {
        radiusList.add(0);
        return;
    }

    while (v != v1) {
        radius = Math.min(radius, Math.max(curDist, dist2 - curDist));
        curDist += parent.get(v)[1];
        v = parent.get(v)[0];
    }

    radiusList.add(radius);
}

• 두 번의 DFS를 통해 현재 독립된 트리의 지름을 계산하고, 중심을 기준으로 반지름을 구해 radiusList에 저장한다.

3. 새로운 길 추가로 최대 통행 시간 최적화

Collections.sort(radiusList, Collections.reverseOrder());

if (radiusList.size() >= 2 && radiusList.get(0) + radiusList.get(1) + L >= ans) {
    ans = radiusList.get(0) + radiusList.get(1) + L;
}
if (radiusList.size() >= 3 && radiusList.get(1) + radiusList.get(2) + 2 * L >= ans) {
    ans = radiusList.get(1) + radiusList.get(2) + 2 * L;
}

• radiusList를 내림차순으로 정렬하고, 𝐿을 추가하여 가능한 최소의 최대 통행 시간을 갱신한다.

So...

이 코드는 독립된 트리의 반지름을 활용하여 효율적으로 새로운 길을 추가하고 최대 통행 시간을 최소화한다. 문제를 해결하기 위해 DFS를 두 번 사용하여 트리의 중심과 반지름을 구했으며, 이 과정에서 시간 복잡도는 𝑂(𝑁+𝑀)을 유지했다. 이 코드를 통해 그래프 탐색과 거리 계산의 중요성을 다시금 확인할 수 있었다.