백준 14938번 [서강그라운드](C++) -yes6686- 티스토리

백준 문제 풀이: 14938 [서강그라운드]

---

문제 링크: https://www.acmicpc.net/problem/14938

문제 설명:

서강대학교의 각 지역에서 아이템을 수집할 수 있으며, 특정 지역 간 이동 거리가 주어집니다. 한 지역에서 다른 지역까지의 이동 거리가 주어진 범위(m)를 초과하지 않는다면 해당 지역의 아이템을 수집할 수 있습니다.

모든 지역을 탐색하여 수집할 수 있는 아이템의 최대 개수를 구하는 문제입니다.

---

문제 해결 코드

#include <iostream>
#include <algorithm>
#define INF 1000000000
using namespace std;

int items[101];        // 각 지역의 아이템 개수
int dist[101][101];    // 지역 간 거리 정보

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, r; // 지역 수, 수색 범위, 길의 수
    cin >> n >> m >> r;

    // 거리 배열 초기화
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i != j) {
                dist[i][j] = INF;
            }
        }
    }

    // 각 지역의 아이템 개수 입력
    for (int i = 1; i <= n; i++) {
        cin >> items[i];
    }

    // 길의 정보 입력
    for (int i = 0; i < r; i++) {
        int a, b, l;
        cin >> a >> b >> l;
        dist[a][b] = l;
        dist[b][a] = l;
    }

    // 플로이드-워셜 알고리즘으로 최단 거리 계산
    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] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }

    // 최대 수집 가능한 아이템 개수 계산
    int maxItems = 0;
    for (int i = 1; i <= n; i++) {
        int totalItems = 0;
        for (int j = 1; j <= n; j++) {
            if (dist[i][j] <= m) {
                totalItems += items[j];
            }
        }
        maxItems = max(maxItems, totalItems);
    }

    // 결과 출력
    cout << maxItems << '\n';

    return 0;
}

---

코드 설명

• 핵심 알고리즘: 플로이드-워셜 알고리즘을 사용하여 모든 지역 간 최단 거리를 계산하고, 이를 기반으로 수집 가능한 아이템의 개수를 구합니다.
• 구현 세부사항:
  • dist[i][j]: 지역 i에서 j까지의 최단 거리
  • 최단 거리 계산 후, 각 지역을 기준으로 수집 가능한 아이템의 총합을 계산
• 시간 복잡도 분석: O(n³)
  • 플로이드-워셜 알고리즘의 시간 복잡도: O(n³)
  • 지역 개수 n이 최대 100이므로 계산 가능

---

결과

모든 지역을 탐색하며 수집할 수 있는 아이템의 최대 개수를 정확히 계산합니다. 플로이드-워셜 알고리즘을 활용하여 효율적으로 풀이했습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!