14938 서강그라운드 Java

14938 서강그라운드 Java

오늘은 내가 골드 2를 달성한 영광스러운 날이다. 이 영광을 룸메이트인 서강대 출신 ○** 양에게 돌린다. (희성이라 성을 밝힐 수 없음)

문제 🌐

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

출력

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

접근 방법

처음 입력을 받을 때 인접 행렬과 인접 리스트 중 무엇을 쓸지 잠시 고민했으나… 가중치를 담기엔 인접 행렬이 편할 것 같아 인접 행렬을 선택했다.

출발점 하나마다 다익스트라 알고리즘을 활용해 주울 수 있는 최대 아이템 개수를 갱신했다. 시간 초과가 날까 봐 걱정했는데 경로를 탐색하는 조건이 탐색 가능 거리 >= 현재까지 오는 데 걸린 거리 + 다음 칸으로 움직이는 거리 였기 때문에 생각보다 오래 걸리지 않았다.

일단 다익스트라 알고리즘을 구현하는 과정에서 멍청한 행동을 했다!!

Node 클래스에 그때까지 먹은 아이템을 저장해서 최대값이 갱신되지 않았다. 그냥 거리 배열을 최대값으로 초기화한 후, 거리 가중치에 따라 최대한 많은 칸을 방문하고, 만약 처음 방문하는 곳이라면 주운 아이템 개수를 더해 주면 됐다.

Node에 담을 것은 지점 번호와 그 지점까지 오는 데 걸어온 거리였다.

for (int i = 1; i <= N; i++) {
	if (graph[now][i] > 0 && dist[i] > dist[now] + graph[now][i] && M >= (graph[now][i] + dist[now])) {
		pq.add(new Node(i, dis + graph[now][i]));
		if (dist[i] == Integer.MAX_VALUE)
			answer += items[i];
		dist[i] = dist[now] + graph[now][i];
	}
}

 

Full Solution

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

public class Main {
	static int N;
	static int M;
	static int R;
	static int[] items;
	static int[][] graph;

	static class Node implements Comparable<Node> {
		int pos;
		int dis;

		public Node(int pos, int dis) {
			super();
			this.pos = pos;
			this.dis = dis;
		}

		public int compareTo(Node o) {
			return Integer.compare(this.dis, o.dis);
		}

		@Override
		public String toString() {
			return "Node [pos=" + pos + ", dis=" + dis + "]";
		}

	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		R = sc.nextInt();
		items = new int[N + 1];
		graph = new int[N + 1][N + 1];
		int answer = 0;
		for (int i = 1; i <= N; i++)
			items[i] = sc.nextInt();
		for (int i = 0; i < R; i++) {
			int x = sc.nextInt();
			int y = sc.nextInt();
			int cost = sc.nextInt();
			graph[x][y] = cost;
			graph[y][x] = cost;
		}

		for (int start = 1; start <= N; start++) {
			answer = Math.max(answer, dijkstra(start));
		}

		System.out.println(answer);

	}

	static int dijkstra(int start) {
		PriorityQueue<Node> pq = new PriorityQueue<>();
		int[] dist = new int[N + 1];
		boolean[] visited = new boolean[N + 1];
		Arrays.fill(dist, Integer.MAX_VALUE);
		dist[start] = 0;
		int answer = items[start];

		pq.add(new Node(start, 0));

		while (!pq.isEmpty()) {
			Node curr = pq.poll();
			int now = curr.pos;
			int dis = curr.dis;
//			System.out.println(curr.toString());

			for (int i = 1; i <= N; i++) {
				if (graph[now][i] > 0 && dist[i] > dist[now] + graph[now][i] && M >= (graph[now][i] + dist[now])) {
					pq.add(new Node(i, dis + graph[now][i]));
					if (dist[i] == Integer.MAX_VALUE)
						answer += items[i];
					dist[i] = dist[now] + graph[now][i];
				}
			}

//			System.out.println("중간 answer: "+answer);

		}
//		System.out.println("answer: "+answer);
//		System.out.println("------------");

		return answer;

	}

}