백준 | 14938번. 서강 그라운드 - 다익스트라 or 플로이드

⬛ 백준 14938번. 서강 그라운드 - 다익스트라 or 플로이드

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

14938번: 서강그라운드

문제

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

지역의 번호는 1이상 n이하의 정수이다. 두 지역의 번호가 같은 경우는 없다.

출력

예은이가 얻을 수 있는 최대 아이템 개수를 출력한다.

---

💚나의 풀이

• 시작점이 따로 주어진 것이 아니고, 각 정점에서 m이내로 갈 수 있는 지역들에 대하여 얻을 수 있는 아이템 최대개수를 구하는 문제 이므로 all-to-all 문제이다.
• 따라서 플로이드와 다익스트라 둘다 풀 수 있는 문제이다.
• 우선 나는 다익스트라로 풀었다.
• solution 함수에 시작 정점을 받으면 해당 정점을 기준으로 다른 모든 정점에 대한 최단 거리 distance배열을 세팅하고, 마지막에 for문을 1~n까지만 돌면서 기준값이었던 m 이내의 거리에 존재하는 지역의 인덱스값을 ArrayList에 담아서 리턴시켰다.
• main에서는 for문을 돌면서 1~n을 차례로 시작점으로 하여 solution을 호출하고, 리턴받은 리스트를 순회하면서 해당 인덱스의 item 개수를 누적하다가. 기존 max보다 큰 값 나타나면 갱신되는 식으로 처리했따.
• 마지막에는 max값이 최종 최대 아이템 개수가 된다.

package to_0902_1;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

/*백준 14938번. 서강 그라운드 - 플로이드 or 다익스트라 풀이 가능 */
public class Main {
	static int n, m, r;//정점, 기준값, 간선 순
	static int[] item;//각 정점별 얻을 수 있는 아이템 수
	static ArrayList<ArrayList<int[]>> graph;
	
	//솔루션 함수 - 다익스트라 + 솔루션 
	static ArrayList<Integer> solution(int st) {
	
		boolean[] visited = new boolean[n+1];//양방향이라 체크
		int[] distance = new int[n+1];
		Arrays.fill(distance, Integer.MAX_VALUE);
		//가중치 우선 정렬 
		PriorityQueue<int[]> pQ = new PriorityQueue<>((a, b) -> a[1]-b[1]);
		
		//시작점 초기화
		distance[st] = 0;
		pQ.offer(new int[] {st, 0}); //시작 -> 끝 -> 가중치 
		//cur[0]이 e , cur[1] 이 가중치
		while(!pQ.isEmpty()) {
			int[] cur = pQ.poll();
			if(visited[cur[0]]) continue;
			visited[cur[0]] = true;
			
			for(int [] nx : graph.get(cur[0])) {//다음 정점에 대하여
				if(!visited[nx[0]] && distance[nx[0]] > distance[cur[0]] + nx[1]) {
					distance[nx[0]] = distance[cur[0]] + nx[1];
					pQ.offer(new int[] {nx[0], distance[nx[0]]});
				}
			}
		}
		//m이내의 거리에 해당하는 정점들만 보내기 
		ArrayList<Integer> answer = new ArrayList<>();
			
		for(int i=1; i<=n; i++) {
			if(distance[i] > m) continue;
			
			answer.add(i); //m이내의 거리에 존재하는 정점들만 보냄
		}
		return answer;
	}
	
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		
		n = kb.nextInt();
		m = kb.nextInt();//얘 걍 기준값
		r = kb.nextInt();
		
		item = new int[n+1];
		graph = new ArrayList<>();
		for(int i=0; i<=n; i++) {
			graph.add(new ArrayList<>());
		}
		//아이템 입력받기 
		for(int i=1; i<=n; i++) {
			item[i] = kb.nextInt();
		}
		
		//그래프 정보 입력
		for(int i=0; i<r; i++) {
			int a = kb.nextInt();
			int b = kb.nextInt();
			int c = kb.nextInt();
			//양바향 
			graph.get(a).add(new int[] {b, c});
			graph.get(b).add(new int[] {a, c});
		}
		int max = Integer.MIN_VALUE;
		
		for(int i=1; i<=n; i++) {
			int sum = 0;
			//각각의 1~n까지 차례로 호출하여 시작정점 기준 호출하고 
			for(int x : solution(i)) {//리턴받은 인덱스에 대하여 
				
				sum += item[x];//각 해당하는 정점에 대한 아이템 개수 누적하고 
			}
			
			max = Math.max(max, sum);//그 중 가장 최대 개수를 세팅 
		}
		//정답 출력
		System.out.println(max);	
	}
}