백준 14938 - 서강 그라운드

Java

14938 번 - 서강 그라운드

문제

접근 방법

플로이드 - 와샬로 해결 할 수 있는 문제였다.

각 노드에서 모든 노드의 최단거리를 구한다.
이후 각 노드 별로 다른 노드까지 거리 중 m보다 작은 노드의 아이템 수를 합하여, 최대 아이템 수를 구한다.

코드

import java.util.*;
import java.io.*;

public class Main {
	static int n, m, r, result;
	static int MAX_VALUE = 999999999 ;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	n = stoi(stk.nextToken());
    	m = stoi(stk.nextToken());
    	r = stoi(stk.nextToken());
    	
    	int[][] graph = new int[n + 1][n + 1];
    	int[] node = new int[n + 1];
    	
    	// 그래프 세팅. 
    	for(int i = 1; i <= n; i++) {
    		Arrays.fill(graph[i], MAX_VALUE);
    		graph[i][i] = 0;
    	}
    	
    	// 아이템 수 세팅
    	stk = new StringTokenizer(br.readLine());
    	for(int i = 1; i <= n; i++) {
    		node[i] = stoi(stk.nextToken());
    	}
    	
    	// 길 세팅
    	int a,b,c;
    	for(int i = 0; i < r; i++) {
    		stk = new StringTokenizer(br.readLine());
    		a = stoi(stk.nextToken());
    		b = stoi(stk.nextToken());
    		c = stoi(stk.nextToken());
    		
    		graph[a][b] = c;
    		graph[b][a] = c;
    	}
    	
    	// 플로이드 와샬 사용
    	for(int i = 1; i <= n; i++) {
    		for(int j = 1; j <= n; j++) {
    			if(i == j)
    				continue;
    			for(int k = 1; k <= n; k++) {
    				if(graph[j][k] > graph[j][i] + graph[i][k])
    					graph[j][k] = graph[j][i] + graph[i][k];
    			}
    		}
    	}
    	int sum = 0;
    	for(int i = 1; i <= n; i++) {
    		sum = 0;
    		for(int j = 1; j <= n; j++) {
    			if(i == j) {
    				sum += node[i];
    				continue;
    			}
    			if(graph[i][j] <= m)
    				sum += node[j];
    		}
    		
    		result = Math.max(sum, result);
    	}
    	System.out.println(result);
    	br.close();
	}
	
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

개선할 점