[ 백준 ] 14938 서강그라운드

Link | 14938번 문제 : 서강그라운드

📌 Analyze

먼저 모든 구역에서 다른 모든 구역으로 가는 최단 거리를 구해야 한다.

이는 Floyd Warshall Algorithm으로 해결할 수 있다.

이후 각 구역을 탐색하며 아이템을 먹을 수 있는 거리의 item들을 합한다.

이 때 가장 많은 아이템을 먹을 수 있는 구역이 떨어져야 하는 구역이다.

여기서는 떨어지는 구역이 아니라 가장 많이 먹은 아이템 수를 출력하면 된다.

📌 Solution

Step 1. 초기화

앞으로의 연산을 위해서 초기화를 적절히 하는 것이 중요하다.

int Z;

int[][] field = new int[Z + 1][Z + 1];
int[] items = [Z + 1];

위에서 Z는 구역의 갯수, field는 구역 간의 거리, items는 구역의 아이템 갯수이다.

Z는 주어진 값을 통해 초기화한다.

field는 우선 [i][i] = 0 너머지는 INF으로 초기화해야 한다.

이 때 INF를 Integer.MAX_VALUE로 하면 이후 처리에 문제가 생긴다.

Z개의 구역이 있을 때 다른 구역으로 가는 최대 거리는 15 * (Z - 1)이다.

그렇기 때문에 INF = 15 * (Z - 1) + 1로 한다.

field = new int[Z + 1][Z + 1];
int INF = 15 * (Z - 1) + 1;
for (int r = 1; r <= Z; r++) {
    for (int c = 1; c <= Z; c++) {
        if (r == c) field[r][c] = 0;
        else field[r][c] = field[c][r] = INF;
    }
}

items는 구역을 index으로 하여 주어진 값을 저장하면 된다.

items = Arrays.stream(("0 " + reader.readLine()).split(" "))
        .mapToInt(Integer::parseInt)
        .toArray();

이후로는 주어진 거리들을 저장하면 된다.

이 때 양방향 그래프라는 것을 유념해야 한다.

while (L-- > 0) {
    tokenizer = new StringTokenizer(reader.readLine());
    int zoneA = Integer.parseInt(tokenizer.nextToken());
    int zoneB = Integer.parseInt(tokenizer.nextToken());
    int range = Integer.parseInt(tokenizer.nextToken());
    field[zoneA][zoneB] = field[zoneB][zoneA] = range;
}

Step 2. Floyd Warshall

초기화가 되었으면 Floyd Warshall 알고리즘을 통해 최단 거리를 구한다.

for (int pass = 1; pass <= Z; pass++
    for (int from = 1; from <= Z; from++
        for (int to = 1; to <= Z; to++
            if (field[from][to] > field[from][pass] + field[pass][to]
                field[from][to] = field[to][from] = field[from][pass] + field[pass][to];

Step 3. 최대 아이템

이제 각 구역을 기준으로 얻을 수 있는 최대 아이템을 구한다.

이 때 갈 수 없는 구역은 제외한다.

int max = Integer.MIN_VALUE;
for (int r = 1; r <= Z; r++) {
    int sum = 0;
    for (int c = 1; c <= Z; c++) {
        if (field[r][c] <= R) sum += items[c];
    }
    max = Math.max(max, sum);
}
return max;

📌 Code

GitHub Repository

private static int Z, R;
private static int[][] field;
private static int[] items;

private static void solution() throws IOException {
    init();
    optimizeRange();
    result.append(maxItem());
}

private static void init() throws IOException {
    StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
    Z = Integer.parseInt(tokenizer.nextToken());
    R = Integer.parseInt(tokenizer.nextToken());
    int L = Integer.parseInt(tokenizer.nextToken());

    field = new int[Z + 1][Z + 1];
    int INF = 15 * (Z - 1) + 1;
    for (int r = 1; r <= Z; r++) {
        for (int c = 1; c <= Z; c++) {
            if (r == c) field[r][c] = 0;
            else field[r][c] = field[c][r] = INF;
        }
    }

    items = Arrays.stream(("0 " + reader.readLine()).split(" "))
            .mapToInt(Integer::parseInt)
            .toArray();

    while (L-- > 0) {
        tokenizer = new StringTokenizer(reader.readLine());
        int zoneA = Integer.parseInt(tokenizer.nextToken());
        int zoneB = Integer.parseInt(tokenizer.nextToken());
        int range = Integer.parseInt(tokenizer.nextToken());
        field[zoneA][zoneB] = field[zoneB][zoneA] = range;
    }
}

private static void optimizeRange() {
    for (int pass = 1; pass <= Z; pass++)
        for (int from = 1; from <= Z; from++)
            for (int to = 1; to <= Z; to++)
                if (field[from][to] > field[from][pass] + field[pass][to])
                    field[from][to] = field[to][from] = field[from][pass] + field[pass][to];
}

private static int maxItem() {
    int max = Integer.MIN_VALUE;
    for (int r = 1; r <= Z; r++) {
        int sum = 0;
        for (int c = 1; c <= Z; c++) {
            if (field[r][c] <= R) sum += items[c];
        }
        max = Math.max(max, sum);
    }
    return max;
}