백준 14938 서강그라운드(JAVA)

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

14938번: 서강그라운드

문제풀이 방법

먼저 다익스트라 알고리즘을 공부하고 싶다면 아래의 문제를 한번 풀어보는 것을 추천한다.

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

1753번: 최단경로

다익스트라 알고리즘을 알고있다는 가정하에 설명을 하자면, 시작정점이 있지 않기 때문에 모든 정점에서 시작했을 때의 아이템의 최대 개수를 알아야한다.

for(int i =1;i<=n;i++) {
			visited = new boolean[n+1];
			Arrays.fill(w, INF);
			int k = Dekestr(i, w);
			if(max<k) max = k;
		}

위의 코드가 모든 정점을 시작정점으로 하여 최대 값을 찾는 부분이다.

그리고 다익스트라 알고리즘에서 다익스트라 알고리즘이 끝나고 각 정점의 가중치를 수색범위 M과 비교하여 M이하인 정점들의 아이템을 더하는 방법을 사용했다.

for(int i =1;i<=n;i++) {
			if(w[i] <= m) {
				item_value += value[i];
			}
		}

 

 

전체 코드

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {	
	static List<Node>[] list;
	static boolean visited[];
	static int n;
	static int m;
	static int r;
	static int value[];
	static int INF = Integer.MAX_VALUE;
	static class Node implements Comparable<Node>{
		int next = 0;
		int distance= 0;
		public Node(int next, int distance) {
			this.next = next;
			this.distance = distance;
		}
		@Override
		public int compareTo(Node o) {
			return this.distance - o.distance;
		}
		
	}
	static int Dekestr(int start, int[]w){
		PriorityQueue<Node> queue = new PriorityQueue<>();
		queue.add(new Node(start,0));
		w[start] = 0;
		int item_value = 0;
		while(!queue.isEmpty()) {
			Node node = queue.poll();
			int v = node.next;
			if(visited[v]) continue;
			visited[v] = true;
			for(Node next: list[v]) {
				if(w[v] + next.distance > m) continue;
				if(w[next.next]> w[v] + next.distance) {
					w[next.next] = w[v] + next.distance;
					queue.add(new Node(next.next, w[next.next]));
				}
			}
		}
		for(int i =1;i<=n;i++) {
			if(w[i] <= m) {
				item_value += value[i];
			}
		}
		return item_value;
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine() + " ");
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		r= Integer.parseInt(st.nextToken());
		list = new ArrayList[n+1];
		visited = new boolean[n+1];
		int[] w = new int[n+1];
		int[] w1 = new int[n+1];
		for(int i =1; i<=n;i++) {
			list[i] = new ArrayList<>();
		}
		value = new int[n + 1];
		StringTokenizer st1 = new StringTokenizer(br.readLine() + " ");
		for(int i=1;i<=n;i++) {
			value[i] = Integer.parseInt(st1.nextToken());
		}
		for(int i =0; i<r;i++) {
			StringTokenizer st2 = new StringTokenizer(br.readLine() + " ");
			int a = Integer.parseInt(st2.nextToken());
			int b = Integer.parseInt(st2.nextToken());
			int l = Integer.parseInt(st2.nextToken());
			list[a].add(new Node(b,l));
			list[b].add(new Node(a,l));
		}
		int max = 0;
		for(int i =1;i<=n;i++) {
			visited = new boolean[n+1];
			Arrays.fill(w, INF);
			int k = Dekestr(i, w);
			if(max<k) max = k;
		}
		System.out.print(max);
	}
}