[자바] 백준 14938 - 서강그라운드 (java)

목차

문제 : boj14938

 

 

필요 알고리즘

• 플로이드-워셜 (floyd-warshall)
  
  • 플로이드 워셜을 안다면 쉽게 풀 수 있는 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  플로이드 워셜은 O(N^3)인 알고리즘이지만, 모든 정점에서 모든 정점으로의 최단거리를 알 수 있어서 아주 강력한 알고리즘이다. 심지어 코드도 엄청나게 간단하고 이해하기도 직관적이라 익히기도 쉽다! 모른다면 이번 기회에 익혀보자. 물론 다익스트라로도 풀 수 있는 문제긴하다.

 

  플로이드 워셜을 알고 있다는 가정하에 로직은 이하와 같다.

 

1. 모든 지역에서 모든 지역으로의 최단거리를 플로이드 워셜로 측정한다. O(N^3)

2. '1'에서 만들어둔 데이터를 기준으로 각 지역에서 모든 지역으로의 최단거리를 확인해서 m 이하라면 각 지역별로 총합을 구해준다.

3. '2'에서 구한 총합 중 가장 큰 값을 출력해주면 된다.

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<16);
    static final int INF = 100*30+1;
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    private void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int r = Integer.parseInt(st.nextToken());

        int[] item = new int[n+1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) item[i] = Integer.parseInt(st.nextToken());

        int[][] dist = new int[n+1][n+1];
        for (int[] row : dist) Arrays.fill(row, INF);
        while (r-->0) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int len = Integer.parseInt(st.nextToken());

            dist[a][b] = dist[b][a] = len;
        }

        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }

        int answer = 0;
        for (int i = 1; i <= n; i++) {
            int sum = item[i];

            for (int j = 1; j <= n; j++) {
                if (i==j || dist[i][j] > m) continue;

                sum += item[j];
            }

            answer = Math.max(answer, sum);
        }

        System.out.println(answer);
    }
}