문제 설명
예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 하는 게임이다. 서강그라운드에서 1등을 하면 보상으로 치킨을 주는데, 예은이는 단 한번도 치킨을 먹을 수가 없었다. 자신이 치킨을 못 먹는 이유는 실력 때문이 아니라 아이템 운이 없어서라고 생각한 예은이는 낙하산에서 떨어질 때 각 지역에 아이템 들이 몇 개 있는지 알려주는 프로그램을 개발을 하였지만 어디로 낙하해야 자신의 수색 범위 내에서 가장 많은 아이템을 얻을 수 있는지 알 수 없었다.
각 지역은 일정한 길이 l (1 ≤ l ≤ 15)의 길로 다른 지역과 연결되어 있고 이 길은 양방향 통행이 가능하다. 예은이는 낙하한 지역을 중심으로 거리가 수색 범위 m (1 ≤ m ≤ 15) 이내의 모든 지역의 아이템을 습득 가능하다고 할 때, 예은이가 얻을 수 있는 아이템의 최대 개수를 알려주자.
주어진 필드가 위의 그림과 같고, 예은이의 수색범위가 4라고 하자. ( 원 밖의 숫자는 지역 번호, 안의 숫자는 아이템 수, 선 위의 숫자는 거리를 의미한다) 예은이가 2번 지역에 떨어지게 되면 1번,2번(자기 지역), 3번, 5번 지역에 도달할 수 있다. (4번 지역의 경우 가는 거리가 3 + 5 = 8 > 4(수색범위) 이므로 4번 지역의 아이템을 얻을 수 없다.) 이렇게 되면 예은이는 23개의 아이템을 얻을 수 있고, 이는 위의 필드에서 예은이가 얻을 수 있는 아이템의 최대 개수이다.
입력
첫째 줄에는 지역의 개수 n (1 ≤ n ≤ 100)과 예은이의 수색범위 m (1 ≤ m ≤ 15), 길의 개수 r (1 ≤ r ≤ 100)이 주어진다.
둘째 줄에는 n개의 숫자가 차례대로 각 구역에 있는 아이템의 수 t (1 ≤ t ≤ 30)를 알려준다.
세 번째 줄부터 r+2번째 줄 까지 길 양 끝에 존재하는 지역의 번호 a, b, 그리고 길의 길이 l (1 ≤ l ≤ 15)가 주어진다.
출력
예은이가 얻을 수 있는 최대 아이템 개수를 출력한다.
문제 풀이
- 각 지역과 다른 지역에 연결 되어있는 길의 정보를 인접 행렬에 저장한다.
(양방향 통행이 가능하므로 양쪽에 값을 넣어주기) - 인접 행렬에 플로이드 와샬 알고리즘을 적용해 각 지역 사이의 최단거리를 갱신한다.
- 각 지역 사이의 최단거리를 이용해 얻을 수 있는 최대 아이템 개수를 찾는다.
(모든 지역을 각각 낙하한 지역으로 가정하고 얻을 수 있는 아이템 개수를 구함)
소스 코드
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());
// 각 구역에 있는 아이템의 수
st = new StringTokenizer(in.readLine(), " ");
int item[] = new int[n+1];
for (int i = 1; i <= n; i++) {
item[i] = Integer.parseInt(st.nextToken());
}
// 각 구역에 연결된 길의 정보
int adj[][] = new int[n+1][n+1];
for (int i = 1; i <= n; i++) {
adj[i][i] = -1;
}
int a, b, l;
for (int i = 0; i < r; i++) {
st = new StringTokenizer(in.readLine(), " ");
a = Integer.parseInt(st.nextToken());
b = Integer.parseInt(st.nextToken());
l = Integer.parseInt(st.nextToken());
adj[b][a] = adj[a][b] = l;
}
// 각 구역 사이의 최단거리 찾기
for (int i = 1; i <= n; i++) { // 경유지
for (int start = 1; start <= n; start++) { // 출발지
if (i == start) continue;
for (int end = 1; end <= n; end++) { // 도착지
if (start == end || i == end) continue;
// 현재 경유한 값이 더 짧으면 갱신
if (adj[start][i] == 0 || adj[i][end] == 0) continue;
if (adj[start][i]+adj[i][end] < adj[start][end] || adj[start][end] == 0)
adj[start][end] = adj[start][i]+adj[i][end];
}
}
}
// 얻을 수 있는 최대 아이템 개수 찾기
int max = 0, sum;
for (int i = 1; i <= n; i++) {
sum = 0;
for (int j = 1; j <= n; j++) {
if (adj[i][j] <= m && adj[i][j] != 0) sum += item[j];
}
max = Math.max(max, sum);
}
System.out.println(max);
}느낀 점
이번 문제는 플로이드 와샬 알고리즘을 적용하면 어렵지 않게 해결할 수 있다. 그치만 나는 이번에도 살~짝 삽질을 했지 S(●'ㅅ'●)z 쉽게만 살아가면 재미없어 빙고...
아무튼 나의 삽질은 스터디원들의 도움을 받아서 해결했는데, 내 코드의 문제는 처음에 얻을 수 있는 최대 아이템 개수를 찾을 때 자기 지역을 탐색하는 경우와 탐색을 할 수 없는 경우가 모두 0으로 설정 되어있어서... 탐색할 수 없는 놈들이 값에 포함 돼서 그랬다🥲 그래서 자기 지역을 탐색하는 경우에 미리 값을 -1로 초기화 해주고 답을 구하는 코드로 수정했더니 맞았다.
아무튼 이번 문제 삽질하면서 플로이드 와샬 알고리즘에 대해 조금이라도 더 알게된 것 같아서 그건 좋다. 앞으로는 삽질 하지 말고 생각 잘 하고 문제를 풀자^^... 그리고 반례 만들기!!! 제발 노력하자ㅠㅠ 이번에도 스터디원이 반례 찾아줌ㅠ 다음엔 스스로 할 수 있길🔥
