백준 14938번

2017 Sogang Programming Contest - Master 문제

문제 해설이 아닌 풀이하면서 거쳐간 생각들을 기록하는 글입니다.

문제

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

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

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

입력

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

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

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

출력

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

접근 과정

그래프를 탐색하여 최대로 얻을 수 있는 아이템 수를 구하는 문제이다. 노드와 간선이 최대 100개씩 밖에 안되므로 어떤 그래프 탐색 알고리즘을 사용하더라도 해결할 수 있을 것으로 보였다. 본인은 플로이드 와샬 알고리즘과와 DFS 탐색 알고리즘 두 가지 방법으로 구현하였는데 BFS나 다익스트라 어떤 방법을 사용하더라도 문제를 해결할 수 있다.
처음 플로이드 와샬 알고리즘으로 문제를 풀 때 영문도 모른 채 여러 번 탈락했는데 이유는 동일한 노드를 연결하는 간선이 두 개 이상 입력되었기 때문이었다.
graph[a][b] = std::min(graph[a][b], dist);
처럼 간선을 입력받을 때 항상 길이가 최소가 되는 간선만을 저장하지 않으면 나중에 입력된 간선에 의해 최소 길이 간선이 덮어씌우질 수 있다. 그래프 문제를 풀 때 자연스럽게 노드 간 간선이 하나라고 생각하지 않도록 항상 유의할 필요가 있을 것 같다.
DFS 알고리즘을 통해 구현은 조금 까다로웠는데 방문 기록을 true, false로만 기록하며 방문하도록 구현했을 때 탐색 순서에 따라 최소 거리를 만족하지 못하는 탐색 결과가 나오기도 한다. 이를 해결하기 위해 방문 기록을 bool 대신 이동 거리를 기록하도록 수정하여 해결하였다.

소스 코드

플로이드 와샬

#include <cmath>
#include <cstring>
#include <iostream>

#define INF 0x3F3F3F3F

int main() {
    std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr);

    int n, range, e;
    int graph[101][101];
    int items[101];

    memset(graph, 0x3F, sizeof(graph));

    std::cin >> n >> range >> e;
    for (int i = 1; i <= n; ++i) {
        std::cin >> items[i];
        graph[i][i] = 0;
    }

    for (int i = 0; i < e; ++i) {
        int a, b, dist;
        std::cin >> a >> b >> dist;
        graph[a][b] = std::min(graph[a][b], dist);
        graph[b][a] = std::min(graph[b][a], dist);
    }
    
    for (int mid = 1; mid <= n; ++mid) {
        for (int from = 1; from <= n; ++from) {
            for (int to = 1; to <= n; ++to) {        
                graph[from][to] = std::min(graph[from][to], graph[from][mid] + graph[mid][to]);
            }
        }
    }

    int maxTotal = 0;
    for (int from = 1; from <= n; ++from) {
        int total = 0;
        for (int to = 1; to <= n; ++to) {
            if (graph[from][to] <= range) {
                total += items[to];
            }
        }
        
        maxTotal = std::max(maxTotal, total);
    }
    
    std::cout << maxTotal;
    return 0;
}

DFS

#include <cmath>
#include <cstring>
#include <iostream>

#define INF 0x3F3F3F3F

int n, range, e;
int graph[101][101];
int items[101];
int visitedDist[101];

int getMaxItem(int current, int dist) {
    int item = 0;
    if (visitedDist[current] >= INF) {
        item = items[current];
    }
    visitedDist[current] = dist;

    for (int to = 1; to <= n; ++to) {
        if (current == to) { continue; }
        int distance = dist + graph[current][to];
        if (distance < visitedDist[to] && distance <= range) {
            item += getMaxItem(to, distance);
        }
    }

    return item;
}

int main() {
    std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr);
    memset(graph, 0x3F, sizeof(graph));

    std::cin >> n >> range >> e;
    for (int i = 1; i <= n; ++i) {
        std::cin >> items[i];
    }

    for (int i = 0; i < e; ++i) {
        int a, b, dist;
        std::cin >> a >> b >> dist;
        graph[a][b] = std::min(graph[a][b], dist);
        graph[b][a] = std::min(graph[b][a], dist);
    }

    int maxTotal = 0;
    for (int from = 1; from <= n; ++from) {
        memset(visitedDist, 0x3F, sizeof(visitedDist));
        int total = getMaxItem(from, 0);
        maxTotal = std::max(maxTotal, total);
    }

    std::cout << maxTotal;
    return 0;
}