백준 14938번

오늘 풀어본 문제는 백준의 14938번 문제¹이다. 문제 풀이에 사용한 언어는 C++ 이다.

solved.ac 기준 CLASS

CLASS 4

문제 정보

이 문제의 내용과 조건은 다음과 같다.

문제

예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 하는 게임이다. 서강그라운드에서 1등을 하면 보상으로 치킨을 주는데, 예은이는 단 한번도 치킨을 먹을 수가 없었다. 자신이 치킨을 못 먹는 이유는 실력 때문이 아니라 아이템 운이 없어서라고 생각한 예은이는 낙하산에서 떨어질 때 각 지역에 아이템 들이 몇 개 있는지 알려주는 프로그램을 개발을 하였지만 어디로 낙하해야 자신의 수색 범위 내에서 가장 많은 아이템을 얻을 수 있는지 알 수 없었다.

각 지역은 일정한 길이 $l$ $(1 \le l \le 15)$ 의 길로 다른 지역과 연결되어 있고 이 길은 양방향 통행이 가능하다. 예은이는 낙하한 지역을 중심으로 거리가 수색 범위 $m$ $(1 \le m \le 15)$ 이내의 모든 지역의 아이템을 습득 가능하다고 할 때, 예은이가 얻을 수 있는 아이템의 최대 개수를 알려주자.

field_example

주어진 필드가 위의 그림과 같고, 예은이의 수색범위가 $4$ 라고 하자. (원 밖의 숫자는 지역 번호, 안의 숫자는 아이템 수, 선 위의 숫자는 거리를 의미한다) 예은이가 $2$ 번 지역에 떨어지게 되면 $1$ 번, $2 $번 (자기 지역), $3$ 번, $5$ 번 지역에 도달할 수 있다. ($4$ 번 지역의 경우 가는 거리가 $3 + 5 = 8 > 4$ (수색범위) 이므로 $4$ 번 지역의 아이템을 얻을 수 없다.) 이렇게 되면 예은이는 $23$ 개의 아이템을 얻을 수 있고, 이는 위의 필드에서 예은이가 얻을 수 있는 아이템의 최대 개수이다.

입력

첫째 줄에는 지역의 개수 $n$ $(1 \le n \le 100)$ 과 예은이의 수색범위 $m$ $(1 \le m \le 15)$, 길의 개수 $r$ $(1 \le r \le 100)$ 이 주어진다.

둘째 줄에는 $n$ 개의 숫자가 차례대로 각 구역에 있는 아이템의 수 $t$ $(1 \le t \le 30)$ 를 알려준다.

세 번째 줄부터 $r+2$ 번째 줄 까지 길 양 끝에 존재하는 지역의 번호 $a$, $b$, 그리고 길의 길이 $l$ $(1 \le l \le 15)$ 가 주어진다.

지역의 번호는 $1$ 이상 $n$ 이하의 정수이다. 두 지역의 번호가 같은 경우는 없다.

출력

예은이가 얻을 수 있는 최대 아이템 개수를 출력한다.

풀이과정

1번째 시도

문제를 보고 또 다른 다익스트라 문제인가 싶었는데, 한 점에서만 다른 점들까지의 거리를 확인하는 것이 아니라, 모든 점에서 확인해야 했기 때문에 플로이드-워셜 알고리즘을 이용하기로 하였다.

플로이드-워셜 알고리즘을 이용하여 각 정점 사이의 거리를 모두 저장한 뒤, 각 정점들을 순회하며 탐색 범위와 거리를 비교하여 아이템의 개수를 합한 후, 최댓값을 취하는 방식으로 문제를 해결하려 시도하였다.

코드는 다음과 같이 작성하였다.

// https://www.acmicpc.net/problem/14938
#include <bits/stdc++.h>

using namespace std;

int graph[101][101] = {0,};
int dist[101][101] = {0,};

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n, m, r;
    int item[101] = {0,};

    cin >> n >> m >> r;

    for (int i=1; i<=n; i++) {
        cin >> item[i];
    }

    for (int i=1; i<=n; i++) {
        for (int j=1; j<=n; j++) {
            if (i != j) {
                graph[i][j] = INT_MAX;
            }
        }
    }

    for (int i=0; i<r; i++) {
        int start, end, weight;

        cin >> start >> end >> weight;
        graph[start][end] = min(graph[start][end], weight);
        graph[end][start] = min(graph[end][start], weight);
    }

    for (int i=1; i<=n; i++) {
        for (int j=1; j<=n; j++) {
            if (i == j) {
                dist[i][j] = 0;
            }
            else {
                dist[i][j] = graph[i][j];
            }
        }
    }

    for(int k=1; k<=n; k++){
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX) {
                    dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]);
                }
            }
        }
    }

    int max_items = 0;
    int temp_items = 0;

    for (int i=1; i<=n; i++) {
        for (int j=1; j<=n; j++) {
            if (dist[i][j] <= m) {
                temp_items += item[j];
            }
        }

        max_items = max(max_items, temp_items);
        temp_items = 0;
    }

    cout << max_items;

    return 0;
}

그러자 모든 테스트 케이스를 통과하고 정답이 나오는 것을 확인할 수 있었다.

마무리

플로이드-워셜 알고리즘은 꽤 오랜만에 사용하는 알고리즘이라서 헤메지 않을까 걱정했는데, 생각보다 문제없이 넘어가서 다행이었다.

문제를 풀면서 처음에 눈치채지 못한게 있었는데, 거리를 더하는 과정에서 두 값이 INT_MAX 일 경우를 고려하지 못했었다. 다행히도 예제 테스트케이스가 이를 감지할 수 있도록 되어있어서 망정이지, 만약 그렇지 않았다면 맞왜틀을 연발할 뻔 했다. 앞으로 INT_MAX 를 사용할 때는 이를 염두에 두어야겠다.

오늘의 PS는 여기까지!

1: https://www.acmicpc.net/problem/14938

← Previous Post Next Post →