[BOJ] 14938 서강 그라운드 - JAVA

1. 문제

14938번: 서강그라운드

각 지역은 일정한 길이 l (1 ≤ l ≤ 15)의 길로 다른 지역과 연결되어 있고 이 길은 양방향 통행이 가능하다. 예은이는 낙하한 지역을 중심으로 거리가 수색 범위 m (1 ≤ m ≤ 15) 이내의 모든 지역의 아이템을 습득 가능하다고 할 때, 예은이가 얻을 수 있는 아이템의 최대 개수를 알려주자.

---

2. 풀이

입력

N,M,R, 아이템 개수를 입력받는다.

양방향이기 때문에 길을 입력받을때 두 가지 모두 저장해둔다. 같은 구간이 여러 번 입력될 수도 있는 경우를 고려해서 road[a][b], road[b][a]에 현재 값과 l의 min값을 저장한다. 이를 위해 road에는 모두 M+1값을 저장한다. (습득가능한 값 +1 = 습득 불가능한 값)

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(in.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int R = Integer.parseInt(st.nextToken());

int[] item = new int[N];
st = new StringTokenizer(in.readLine());
for(int n=0;n<N;n++) item[n] = Integer.parseInt(st.nextToken());

int[][] road = new int[N][N];
for(int n=0;n<N;n++) Arrays.fill(road[n], M+1);

int a,b,l;
for(int r=0;r<R;r++){
   st = new StringTokenizer(in.readLine());
   a = Integer.parseInt(st.nextToken())-1;
   b = Integer.parseInt(st.nextToken())-1;
   l = Integer.parseInt(st.nextToken());

   road[a][b] = Math.min(l,road[a][b]);
   road[b][a] = Math.min(l,road[b][a]);
}

 

탐색(플로이드 워셜)

중간 지점 k를 가장 바깥 반복문에 넣고 시작점 i, 끝점 j를 탐색해가면서 i->k->j와 i->j 중 더 작은 값을 저장한다.

for(int k=0;k<N;k++){
   for(int i=0;i<N;i++){
      for(int j=0;j<N;j++){
         road[i][j] = Math.min(road[i][j], road[i][k]+road[k][j]);
      }
   }
}

 

출력

시작지점 i에서 다른 지역까지 가는 거리를 보고 M보다 작거나 같다면 지역 아이템 개수를 tmp에 더한다.

count에 tmp,count 중 더 큰 값을 저장한다.

int count = 0;
for(int i=0;i<N;i++){
   int tmp = item[i];
   for(int j=0;j<N;j++){
      if(i==j) continue;
      if(road[i][j] <= M) tmp += item[j];
   }
   count = Math.max(count, tmp);
}

System.out.println(count);

 

전체 코드

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

public class BOJ_14938_서강그라운드 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(in.readLine());
      int N = Integer.parseInt(st.nextToken());
      int M = Integer.parseInt(st.nextToken());
      int R = Integer.parseInt(st.nextToken());

      int[] item = new int[N];
      st = new StringTokenizer(in.readLine());
      for(int n=0;n<N;n++) item[n] = Integer.parseInt(st.nextToken());

      int[][] road = new int[N][N];
      for(int n=0;n<N;n++) Arrays.fill(road[n], M+1);

      int a,b,l;
      for(int r=0;r<R;r++){
         st = new StringTokenizer(in.readLine());
         a = Integer.parseInt(st.nextToken())-1;
         b = Integer.parseInt(st.nextToken())-1;
         l = Integer.parseInt(st.nextToken());

         road[a][b] = Math.min(l,road[a][b]);
         road[b][a] = Math.min(l,road[b][a]);
      }

      for(int k=0;k<N;k++){
         for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
               road[i][j] = Math.min(road[i][j], road[i][k]+road[k][j]);
            }
         }
      }

      int count = 0;
      for(int i=0;i<N;i++){
         int tmp = item[i];
         for(int j=0;j<N;j++){
            if(i==j) continue;
            if(road[i][j] <= M) tmp += item[j];
         }
         count = Math.max(count, tmp);
      }

      System.out.println(count);
   }
}

---

3. 결과

다익스트라도 가능했겠지만 이 문제는 플로이드워셜 풀이로 좀 더 간단하게 풀었다.

다익스트라였다면 시작지점별로 여러 번(n번) 탐색해야 했을 것이다.