Seren dev's blog
article thumbnail

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

 

14938번: 서강그라운드

예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을

www.acmicpc.net

1. 풀이

모든 정점에 대해 모든정점까지의 최단거리를 구해야 하기 때문에 그래프 최단거리 알고리즘을 사용했다.

1 <= N <= 100이기 때문에 시간복잡도가 O(N^3)인 플로이드 알고리즘을 사용할 수 있다.

 

1.1. 로직

1. 전역변수 n, m, r 값을 입력받고, items[], dist[][] 배열을 할당한 다음, dist 배열을 MAX 값으로 초기화한다. (i == j인 경우 0으로 초기화)

2. 각 구역에 있는 아이템 수를 입력받아 items[] 배열에 저장하고, 그래프 정보를 인접 배열 dist[][]에 저장한다.

3. 플로이드 알고리즘을 사용하여  모든 정점에 대해  모든 정점까지의 최단거리(dist)를 구한다.

4. 각 정점을 시작점으로 했을 때 얻을 수 있는 아이템 수를 구하여 최종적으로 얻을 수 있는 최대 아이템 수를 구한다.

2. 코드

<java />
import java.io.*; import java.util.*; public class Main { static final int MAX = 10000; static int n, m ,r; static int[][] dist; 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()); // 초기화 n = Integer.parseInt(st.nextToken()); m = Integer.parseInt(st.nextToken()); r = Integer.parseInt(st.nextToken()); dist = new int[n+1][n+1]; items = new int[n+1]; for (int i = 1; i <= n; i++) { Arrays.fill(dist[i], MAX); dist[i][i] = 0; } // 각 구역에 있는 아이템 수 입력받기 st = new StringTokenizer(br.readLine()); for (int i = 1; i <= n; i++) { items[i] = Integer.parseInt(st.nextToken()); } // 그래프 인접 배열 입력받기 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 c = Integer.parseInt(st.nextToken()); dist[a][b] = c; dist[b][a] =c; } floyd(); System.out.println(findMaxItems()); } static void floyd() { for (int k = 1; k <= n; k++) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (dist[i][j] > dist[i][k] + dist[k][j]) { dist[i][j] = dist[i][k] + dist[k][j]; } } } } } // 각 정점을 시작점으로 했을 때 얻을 수 있는 아이템 수를 구하여 // 최종적으로 얻을 수 있는 최대 아이템 수를 반환함 static int findMaxItems() { int max = 0; for (int v = 1; v <= n; v++) { int sum = 0; for (int j = 1; j <= n; j++) { if (dist[v][j] <= m) { sum += items[j]; } } max = Math.max(max, sum); } return max; } }

 

728x90
profile

Seren dev's blog

@Seren dev

포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!