(JAVA) 백준 14938번 : 서강그라운드 --- [다익스트라]

www.acmicpc.net/problem/14938

14938번: 서강그라운드

 

 

안녕하세요.

 

다익스트라 알고리즘 문제 리뷰합니다.

 

해당 문제는 어렵지 않았습니다!

 

 

단, 저도 헷갈렸던 부분이 있습니다.

 

 

밑줄 친 부분에서, 수색 범위 값은 m , 길의 개수는 r 입니다!!!

(조건 값을 r로 했다가 왜틀렸는지 몰랐...)

 

 

바로 솔루션 설명하겠습니다.

 

솔루션

---

  -  우선, 양방향 그래프입니다.

 

  -  다익스트라 결과값 배열은 시작 지점부터 해당 지점까지 이동하는 최소 거리 입니다.

 

  -  그럼 결과값 배열을 어디서 쓰냐?

    ->  해당 지점까지 이동한 최소 거리가 수색 범위인지 확인해서, 수색 범위 이내 값이라면 해당 지점까지 수색이 가능하단 뜻입니다.

 

  -  다익스트라 결과값 배열을 한 바퀴 순회하면서, 수색 범위 이내인지 체크하여 수색 범위 이내인 경우 해당 지점의 아이템 개수를 더합니다.

 

  -  이렇게 더한 누적합 값이 즉, 얻을 수 있는 최대 아이템 개수 입니다. (정답이란 뜻)

 

 

간단하죠?

 

이상입니다.

 

감사합니다!

 

 

 

소스코드

---

 

	package graph;
	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.StringTokenizer;
	// 서강그라운드
	// 다익스트라 알고리즘
	public class p14938 {
	static int n, m, r;
	static int[] items, results;
	static List<Vertex14938>[] graph;
	public static void main(String args[]) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st = new StringTokenizer(br.readLine());
	n = Integer.valueOf(st.nextToken());
	m = Integer.valueOf(st.nextToken()); // 수색 범위
	r = Integer.valueOf(st.nextToken());
	graph = new ArrayList[n + 1];
	items = new int[n + 1]; // index : 1 ~ n
	st = new StringTokenizer(br.readLine());
	for(int i = 1; i <= n; i++) {
	graph[i] = new ArrayList<Vertex14938>();
	items[i] = Integer.valueOf(st.nextToken());
	}
	for(int i = 0; i < r; i++) {
	st = new StringTokenizer(br.readLine());
	int from = Integer.valueOf(st.nextToken());
	int to = Integer.valueOf(st.nextToken());
	int weight = Integer.valueOf(st.nextToken());
	// 양방향 그래프
	graph[from].add(new Vertex14938(to, weight));
	graph[to].add(new Vertex14938(from, weight));
	}
	results = new int[n + 1];
	int result = 0;
	for(int i = 1; i <= n; i++) {
	Arrays.fill(results, Integer.MAX_VALUE);
	result = Math.max(result, dijkstra(i));
	}
	System.out.println(result);
	}
	static int dijkstra(int start) {
	boolean[] visited = new boolean[n + 1];
	PriorityQueue<Vertex14938> pq = new PriorityQueue<>();
	int result = 0;
	pq.offer(new Vertex14938(start, 0));
	results[start] = 0;
	while(!pq.isEmpty()) {
	Vertex14938 v = pq.poll();
	if(visited[v.end]) {
	continue;
	}
	if(v.weight > results[v.end]) {
	continue;
	}
	visited[v.end] = true;
	for(Vertex14938 nextV : graph[v.end]) {
	if(!visited[nextV.end] && nextV.weight + results[v.end] < results[nextV.end]) {
	results[nextV.end] = nextV.weight + results[v.end];
	pq.offer(new Vertex14938(nextV.end, results[nextV.end]));
	}
	}
	}
	for(int i = 1; i <= n; i++) {
	if(results[i] <= m) {
	result += items[i];
	}
	}
	return result;
	}
	}
	class Vertex14938 implements Comparable<Vertex14938> {
	int end;
	int weight;
	Vertex14938(int end, int weight) {
	this.end = end;
	this.weight = weight;
	}
	public int getEnd() {
	return end;
	}
	public void setEnd(int end) {
	this.end = end;
	}
	// 오름차순
	@Override
	public int compareTo(Vertex14938 o) {
	if(this.weight < o.weight) {
	return -1;
	}
	return 1;
	}
	}

view raw p14938.java hosted with ❤ by GitHub