BOJ 9502 - Bones’s Battery 링크
(2023.05.15 기준 P5)

문제

N개의 학교, M개의 도로가 있다. 학교마다 충전소가 있으며, 이 충전소를 이용해 전기 셔틀 버스의 배터리를 충전한다. 최대 K번의 재충전을 할 수 있을 때, 최소가 되는 전기 셔틀 버스의 범위 출력

알고리즘

범위와 재충전 횟수는 정해져 있지 않고 반비례한다. 재충전 횟수가 최대 K이므로 범위를 이분 탐색으로 정하여 재충전 횟수를 계산한다. 계산할 때에는 플로이드 워셜.

풀이

먼저 학교 간 거리를 플로이드 워셜로 계산하자. N은 최대 100이라서 충분하다.

만약, 전기 셔틀 버스의 범위가 줄어든다면? 재충전 횟수는 늘어난다. 반대로 범위가 커지면 재충전 횟수는 줄어든다.
여기서 우린 재충전 횟수는 최대 K번이라는 정보를 가지고 있다. 최대 재충전 횟수를 넘지 않게끔 거리를 최대한 줄여야 한다. 이는 이분 탐색을 이용하여 임의로 거리를 정하고 재충전 횟수를 구해서 범위를 좁혀나가면 된다.

여기서 재충전 횟수를 어떻게 정해야 할까?
앞에서 구했던 학교 간의 거리 행렬로 하여금 이분 탐색에서의 mid 값보다 같거나 작다면? 한 번의 배터리 충전으로 갈 수 있음을 뜻한다.
이를 이용해 거리[i][j] 값이 mid 값보다 같거나 작다면 1, 아니면 inf로 채운 행렬을 이용해 다시 플로이드 워셜을 돌리면 각 학교 쌍마다 몇 번의 배터리 충전으로 도달할 수 있는지 구할 수 있다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll inf = 1e16;

void solve(){
    int N, K, M;
    cin >> N >> K >> M;

    ll dist[N][N]; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) dist[i][j] = inf;
    for (int i = 0, u, v, d; i < M; i++){
        cin >> u >> v >> d;
        dist[u][v] = dist[v][u] = d;
    }

    // 플로이드 워셜
    for (int k = 0; k < N; k++){
        dist[k][k] = 0;
        for (int i = 0; i < N; i++) for (int j = 0; j < N; j++)
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
    }

    // 이분 탐색
    ll st = 1, en = 1e12;
    while (st < en){
        ll mid = (st + en) >> 1;
        ll matrix[N][N]; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) matrix[i][j] = inf;

        // mid보다 짧거나 같으면 충전 한번에 갈 수 있는 거리
        for (int i = 0; i < N - 1; i++) for (int j = i + 1; j < N; j++)
            if (dist[i][j] <= mid) matrix[i][j] = matrix[j][i] = 1;

        // 플로이드 워셜
        for (int k = 0; k < N; k++){
            matrix[k][k] = 0;
            for (int i = 0; i < N; i++) for (int j = 0; j < N; j++)
                matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j]);
        }

        // 최대 충전 횟수를 구해 K랑 비교해 범위를 좁혀나간다.
        ll recharging = 0;
        for (int i = 0; i < N - 1; i++) for (int j = i + 1; j < N; j++)
            recharging = max(recharging, matrix[i][j]);
        if (recharging <= K) en = mid;
        else st = mid + 1;
    }

    cout << st << '\n';
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int T;
    cin >> T;
    while (T--) solve();
}

• Python

import sys; input = sys.stdin.readline
from math import inf

for _ in range(int(input())):
    N, K, M = map(int, input().split())
    dist = [[inf] * N for _ in range(N)]

    for _ in range(M):
        u, v, d = map(int, input().split())
        dist[u][v] = dist[v][u] = d

    # 플로이드 워셜
    for k in range(N):
        dist[k][k] = 0
        for i in range(N):
            for j in range(N):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    # 이분 탐색
    start = 1; end = 1000000000000
    while start < end:
        mid = (start + end) >> 1
        matrix = [[inf] * N for _ in range(N)]

        # mid보다 짧거나 같으면 충전 한번에 갈 수 있는 거리
        for i in range(N - 1):
            for j in range(i + 1, N):
                if dist[i][j] <= mid:
                    matrix[i][j] = matrix[j][i] = 1

        # 플로이드 워셜
        for k in range(N):
            matrix[k][k] = 0
            for i in range(N):
                for j in range(N):
                    matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j])

        # 최대 충전 횟수를 구해 K랑 비교해 범위를 좁혀나간다.
        recharging = max(matrix[i][j] for i in range(N - 1) for j in range(i + 1, N))
        if recharging <= K:
            end = mid
        else:
            start = mid + 1

    print(start)