백준 14938번: 서강그라운드(Java, 그래프, 플로이드-워셜)

☑️ 문제

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

✔️관련 알고리즘 개념

플로이드-워셜⭐

☑️ 문제 분석

• 해당 문제는 모든 노드간의 최단거리를 계산을 해야하는 문제이므로 플로이드-워션 개념을 사용하여 문제를 풀면된다.
• 예시입력1을 분석해보면

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

  • 첫 째줄에는 지역개수(n), 수색범위(m), 길의 개수(r)가 주어진다.
  • 둘째줄에는 1번에서 n번 지역까지 아이템 개수가 주어진다. 이는 별도의 items배열을 생성하여 지역별 아이템 개수를 저장해두고 최대 아이템 개수를 계산할 때 이용하면 된다.

    1	2	3	4	5
    5	7	8	2	3

  • 이후 r개의 줄에는 길 정보가 주어져있으므로 인접행렬에 저장한다.
    • 단, 양방향으로 지역간 이동이 가능하므로 꼭 양방향으로 거리 정보를 저장한다.
• 최종 출력

  • 이제 최종 출력은 예은이가 1번~n번 지역에 떨어졌을 때 각각 경우에서 얻을 수 있는 아이템 개수를 계산하고 각 경우에서 얻을 수 있는 아이템 개수가 제일 큰 값을 출력하면 된다.

    int max_item = Integer.MIN_VALUE; // 최대 아이템 개수
            for (int i = 1; i <= n; i++) {
                int sum = 0;
                for (int j = 1; j <= n; j++) {
                    if(distance[i][j] <= m) {
                        sum += items[j];
                    }
                }
                if(max_item < sum) max_item = sum;
            }

☑️ 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int[][] distance; // 거리 배열
    static int[] items; // 지역별 아이템 개수

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()); // 지역 개수
        int m = Integer.parseInt(st.nextToken()); // 수색 범위
        int r = Integer.parseInt(st.nextToken()); // 길의 개수

        // 지역별 아이템 개수 저장
        items = new int[n+1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            items[i] = Integer.parseInt(st.nextToken());
        }

        // 인접 행렬 초기화, i와 j의 값이 같은 곳은 0으로 초기화 나머지는 무한대
        distance = new int[n+1][n+1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if(i == j) distance[i][j] = 0;
                else distance[i][j] = Integer.MAX_VALUE;
            }
        }

        // 길 정보 입력받기
        for (int i = 0; i < r; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int l = Integer.parseInt(st.nextToken());
            if(distance[a][b] > l) {
                distance[a][b] = l;
                distance[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(distance[i][k] != Integer.MAX_VALUE && distance[k][j] != Integer.MAX_VALUE && distance[i][j] > distance[i][k] + distance[k][j])
                        distance[i][j] = distance[i][k] + distance[k][j];
                }
            }
        }

        int max_item = Integer.MIN_VALUE; // 최대 아이템 개수
        for (int i = 1; i <= n; i++) {
            int sum = 0;
            for (int j = 1; j <= n; j++) {
                if(distance[i][j] <= m) {
                    sum += items[j];
                }
            }
            if(max_item < sum) max_item = sum;
        }

        System.out.println(max_item);
    }

}

☑️ 채점 결과 : 틀림 → 맞음

☑️ 어려웠던 점

• 양방향 그래프이므로 거리 정보를 양방향으로 저장했어야 했다.

// 처음엔 단방향 저장
if(distance[a][b] > l) {
    distance[a][b] = l;
}

-------->
// 양방향 거리 
if(distance[a][b] > l) {
    distance[a][b] = l;
    distance[b][a] = l;
}