[백준] 서강그라운드

문제 링크

1. 문제 설명

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

• 출력

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

2. 문제 접근

각 노드에서 모든 노드에 대한 최단 거리를 찾아야 하는 문제이므로 모든 노드 간 최단 거리를 구할 수 있는 플로이드-워셜 알고리즘을 통해 답을 구할 수 있습니다. 한 번의 수행으로 모든 최단 거리를 갱신한 후 각 노드별로 조회하며 거리가 range보다 작으면 sum에 더하는 식으로 노드 별 구할 수 있는 아이템의 최대 개수를 구할 수 있습니다.

또한 노드에 대해 다른 노드로 가는 최단거리를 구해야 하는 문제이므로 한 노드에 대해 다른 노드로 가는 최단거리를 구하는 다익스트라 알고리즘을 모든 노드에 대해 적용해보는 식으로도 풀 수 있습니다. 물론 다익스트라가 코드 길이가 더 길고 구현이 번거로운 만큼 플로이드-워셜 풀이가 좀 더 적절하지만 연습삼아 한 번 풀어봤습니다.

위가 플로이드-워셜, 아래가 다익스트라 풀이입니다. 탐색하는 노드의 개수가 같다 보니 실행 시간에 큰 차이는 없고, 큐를 사용하다 보니 다익스트라의 메모리 사용량이 살짝 더 높습니다.

다음 시간에는 최단 거리를 구하는 알고리즘인 다익스트라, 플로이드-워셜 알고리즘에 대해 알아보도록 할게용

코드

// 플로이드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken()); // 전체 노드의 개수
		int range = Integer.parseInt(st.nextToken()); // 탐색 범위
		int route = Integer.parseInt(st.nextToken()); // 간선의 개수
		
		int[] value = new int[n + 1]; // 아이템 개수 
		st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= n; i++) value[i] = Integer.parseInt(st.nextToken());
		
		int[][] map = new int[n+1][n+1];
		while (route --> 0) { // 그래프 2차원 배열 구현
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			int dist = Integer.parseInt(st.nextToken());
			map[start][end] = map[end][start] = dist;
		}
		// map 초기화
		for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) if (map[i][j] == 0 && i != j) map[i][j] = 100000;
		// 플로이드-워셜 알고리즘
		for (int k = 1; k <= n; k++) {
			for (int i = 1; i <= n; i++) {
				for (int j = 1; j <= n; j++) {
					if (map[i][j] > map[i][k] + map[k][j]) map[i][j] = map[i][k] + map[k][j];
				}
			}
		}
		
		int max = 0;
		// 배열 최대값 구하기
		for (int i = 1; i <= n; i++) {
			int sum = 0;
			for (int j = 1; j <= n; j++) {
				if (map[i][j] <= range) sum += value[j];
			}
			max = Math.max(max, sum);
		}
		System.out.println(max);
		
	}
}

// 다익스트라
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

class Node implements Comparable<Node>{
	int n,d; // n for num, d for dist
	public Node(int n, int d) {
		this.n = n;
		this.d = d;
	}
	@Override
	public int compareTo(Node o) {
		return d - o.d;
	}
	
}

public class Main {
	static int n, range;
	static int[] value;
	static List<Node>[] map;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		range = Integer.parseInt(st.nextToken());
		int route = Integer.parseInt(st.nextToken());
		value = new int[n + 1];
		st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= n; i++) value[i] = Integer.parseInt(st.nextToken());
		map = new ArrayList[n+1]; // 그래프 인접 리스트 구현
		for (int i = 0; i <= n; i++) map[i] = new ArrayList<Node>();
		while (route --> 0) {
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			int dist = Integer.parseInt(st.nextToken());
			map[start].add(new Node(end,dist));
			map[end].add(new Node(start,dist));
		}
		int ans = 0;
		for (int i = 1; i <= n; i++) ans = Math.max(ans, dijikstra(i));
		System.out.println(ans);
	}
	// 다익스트라
	static int dijikstra(int start) {
		int[] dist = new int[n+1];
		Arrays.fill(dist, -1);
		dist[start] = 0; // 시작 지점 거리 = 0
		Queue<Node> queue = new PriorityQueue<>();
		queue.add(new Node(start, 0));
		while (!queue.isEmpty()) {
			Node cur = queue.poll();
			if (dist[cur.n] == -1 || dist[cur.n] < cur.d) continue; // 방문할 수 없거나 최단경로를 갱신할 수 없는 경우
			for (Node next : map[cur.n]) { // 연결된 다음 노드에 대해 최단 경로 갱신
				if (dist[next.n] == -1 || dist[next.n] > dist[cur.n] + next.d) {
					dist[next.n] = dist[cur.n] + next.d;
					queue.offer(new Node(next.n, dist[next.n]));
				}
			}
		}
		int cnt = 0;
		for (int i = 1; i <= n; i++) {
			if (dist[i] != -1 && dist[i] <= range) cnt += value[i];
		}
		return cnt;
	}
}