백준 14938 서강그라운드 Java: Floyd-Warshall로 수색 범위 계산

백준 14938번 ‘서강그라운드’는 어느 지역에 낙하해야 수색 범위 안에서 가장 많은 item을 얻는지 구한다. 모든 시작 지역에서 다른 모든 지역까지의 최단 거리가 필요하고 지역 수가 최대 100이므로 Floyd-Warshall로 전체 쌍 최단 거리를 구하면 단순하다.

• 백준 14938번 서강그라운드

BFS가 아니라 weighted shortest path다

길마다 거리가 다르기 때문에 간선 개수가 적은 경로가 실제 이동 거리도 짧다는 보장이 없다. 일반 BFS는 모든 간선 비용이 같을 때 최단 거리를 구하는 알고리즘이다.

예를 들어 A에서 C로 바로 가는 길의 거리가 10이고 A → B → C의 두 길이 각각 2라면, 간선 수는 직접 경로가 적지만 실제 최단 거리는 4다. 정점을 처음 방문했다는 이유로 다시 보지 않으면 더 짧은 경로를 놓친다.

이 문제는 다음 두 방식이 가능하다.

• 각 지역을 시작점으로 다익스트라 N번 실행
• Floyd-Warshall 한 번으로 모든 지역 쌍 계산

N ≤ 100에서는 O(N³)인 Floyd-Warshall이 충분하고 구현도 짧다.

Floyd-Warshall 점화식

distance[from][to]를 현재까지 알려진 최소 거리라고 하자. middle 지역을 경유할 수 있게 만들 때 다음 값을 비교한다.

distance[from][to]
distance[from][middle] + distance[middle][to]

중간 정점 loop가 가장 바깥에 있어야 “1번부터 middle번까지의 정점만 경유한 최단 거리”라는 단계가 유지된다.

모든 최단 거리를 구한 뒤 각 시작 지역에서 거리가 수색 범위 M 이하인 지역의 item 수를 합하고 최댓값을 선택한다. 시작 지역의 거리는 0이므로 자기 지역 item도 포함된다.

Java 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    private static final int INF = 1_000_000_000;

    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(
                new InputStreamReader(System.in)
        );
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());

        int regionCount = Integer.parseInt(tokenizer.nextToken());
        int searchRange = Integer.parseInt(tokenizer.nextToken());
        int roadCount = Integer.parseInt(tokenizer.nextToken());

        int[] items = new int[regionCount + 1];
        tokenizer = new StringTokenizer(reader.readLine());

        for (int region = 1; region <= regionCount; region++) {
            items[region] = Integer.parseInt(tokenizer.nextToken());
        }

        int[][] distance = new int[regionCount + 1][regionCount + 1];
        for (int region = 1; region <= regionCount; region++) {
            Arrays.fill(distance[region], INF);
            distance[region][region] = 0;
        }

        for (int road = 0; road < roadCount; road++) {
            tokenizer = new StringTokenizer(reader.readLine());
            int from = Integer.parseInt(tokenizer.nextToken());
            int to = Integer.parseInt(tokenizer.nextToken());
            int length = Integer.parseInt(tokenizer.nextToken());

            distance[from][to] = Math.min(distance[from][to], length);
            distance[to][from] = Math.min(distance[to][from], length);
        }

        for (int middle = 1; middle <= regionCount; middle++) {
            for (int from = 1; from <= regionCount; from++) {
                if (distance[from][middle] == INF) {
                    continue;
                }

                for (int to = 1; to <= regionCount; to++) {
                    if (distance[middle][to] == INF) {
                        continue;
                    }

                    distance[from][to] = Math.min(
                            distance[from][to],
                            distance[from][middle] + distance[middle][to]
                    );
                }
            }
        }

        int answer = 0;

        for (int start = 1; start <= regionCount; start++) {
            int collected = 0;

            for (int region = 1; region <= regionCount; region++) {
                if (distance[start][region] <= searchRange) {
                    collected += items[region];
                }
            }

            answer = Math.max(answer, collected);
        }

        System.out.println(answer);
    }
}

도로 입력에서 Math.min()을 사용하면 같은 두 지역을 잇는 길이 여러 번 들어와도 가장 짧은 값을 보존한다. INF끼리 더하는 상황도 건너뛰어 sentinel 계산이 실제 거리처럼 취급되지 않게 했다.

예제 실행

5 5 4
5 7 8 2 3
1 4 5
5 2 4
3 2 3
1 2 3

2번 지역에 낙하하면 수색 범위 5 안에서 1, 2, 3, 5번 지역의 item을 얻을 수 있다.

5 + 7 + 8 + 3 = 23

따라서 출력은 23이다.

BFS로 35분을 보낸 뒤 바꾼 풀이

원문에는 처음 약 35분 동안 BFS로 접근했다고 적혀 있다. 방문한 지역을 다시 보지 않는 방식에서는 더 짧은 거리로 같은 지역에 도착할 가능성을 놓친다는 점을 뒤늦게 발견했고, 문제 분류를 확인한 뒤 Floyd-Warshall로 바꿨다.

입력의 m은 수색 범위이고 r은 길의 수인데 두 값을 혼동해 약 3분 동안 오답 원인을 찾기도 했다. 문제를 읽고 접근해서 통과하기까지 원문에 기록된 전체 시간은 약 50분이었다.

한 출발점만 필요한 경우의 다익스트라는 백준 1916 최소비용 구하기, 모든 정점까지의 다익스트라 구현은 백준 1753 최단경로에서 비교할 수 있다.

복잡도와 검증 범위

Floyd-Warshall은 시간 O(N³), 거리 행렬 공간 O(N²)을 사용한다. item 합은 최대 100 × 30 = 3,000이고 최단 거리도 문제 범위에서 int로 충분하다. INF = 1,000,000,000을 실제 경로와 넉넉히 떨어뜨렸다.

Java source를 수동 검토하고 보존된 예제 및 random undirected weighted graph 100개를 시작점별 다익스트라 oracle과 대조했다. 2026년 8월 2일 현재 BOJ URL은 채점 서비스 준비 화면이라 current judge 재제출은 확인하지 못했다.