[백준/boj] 14938: 서강그라운드 (Java) / 다익스트라 알고리즘

문제

14938번: 서강그라운드

전체코드

import java.util.*;
import java.io.*;

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static ArrayList<Vertex>[] graph;
	static int[] distance;
	static boolean[] check;
	static int[] item;
	static int areaCnt,areaLimit,loadCnt;
	
	private static class Vertex implements Comparable<Vertex>{
		int no;
		int dis;
		
		public Vertex(int no, int dis) {
			this.no = no;
			this.dis = dis;
		}

		@Override
		public int compareTo(Vertex o) {
			return this.dis - o.dis;
		}
	}
	
	public static void main(String[] args) throws Exception {
		st = new StringTokenizer(br.readLine());
		areaCnt = Integer.parseInt(st.nextToken());
		areaLimit = Integer.parseInt(st.nextToken());
		loadCnt = Integer.parseInt(st.nextToken());
		graph = new ArrayList[areaCnt+1];
		item = new int[areaCnt+1];
		check = new boolean[areaCnt+1];
		distance = new int[areaCnt+1];
		st = new StringTokenizer(br.readLine());
		for(int i=1; i<=areaCnt; i++) {
			graph[i] = new ArrayList<Vertex>(); // 초기화!!!
			item[i] = Integer.parseInt(st.nextToken());
		}
		for(int i=0; i<loadCnt; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int l = Integer.parseInt(st.nextToken());
			graph[a].add(new Vertex(b,l));
			graph[b].add(new Vertex(a,l));
		}
		int maxNum = 0;
		for(int i=1; i<= areaCnt; i++) {
			maxNum = Math.max(maxNum, djikstra(i));
		}
		System.out.println(maxNum);
	}

	private static int djikstra(int start) {
		int itemTotal =0;
		Arrays.fill(distance, Integer.MAX_VALUE);
		Arrays.fill(check, false);
		
		PriorityQueue<Vertex> queue = new PriorityQueue<Vertex>();
		queue.offer(new Vertex(start, 0));
		distance[start] = 0; // 자기 자신은 거리가 0
		
		while(!queue.isEmpty()) {
			Vertex current = queue.poll();
			int no = current.no;
			
			if(check[no]) continue;
			check[no] = true;
			
			for(Vertex vertex: graph[no]) {
				if(!check[vertex.no] && distance[vertex.no] > distance[no] + vertex.dis) {
					distance[vertex.no] = distance[no]+ vertex.dis;
					queue.offer(new Vertex(vertex.no, distance[vertex.no]));
				}
			}
		}
		
		
		for(int i=1; i<=areaCnt; i++) {
			if(distance[i] <= areaLimit) {
				itemTotal+= item[i];
			}
		}
		return itemTotal;
	}
}

풀이

Vertex 클래스

지역의 번호(no)와 시작 지역부터 no까지의 거리(dis)를 담는다.

	private static class Vertex implements Comparable<Vertex>{
		int no;
		int dis;
		
		public Vertex(int no, int dis) {
			this.no = no;
			this.dis = dis;
		}

		@Override
		public int compareTo(Vertex o) {
			return this.dis - o.dis;
		}
	}

• no => 지역 번호
• dis => 시작 정점(지역)으로 부터 no까지의 거리
• compareTo 함수 => 거리 기준 오름차순 정렬을 위한 함수 (PriorityQueue에서 사용됨, poll() 하면 dis가 작은것부터 poll()된다.)

사용되는 배열

graph = new ArrayList[areaCnt+1];
item = new int[areaCnt+1];
check = new boolean[areaCnt+1];
distance = new int[areaCnt+1];

• graph: 지역 연결 정보를 담고있다.

		for(int i=0; i<loadCnt; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int l = Integer.parseInt(st.nextToken());
			graph[a].add(new Vertex(b,l));
			graph[b].add(new Vertex(a,l));
		}

a와 b가 이어졌을때 a에도 add하고, b에도 add한다. (양방향 연결) 

양방향 연결로 모두 담기면 아래 그림1과 같은 모습이 된다.

 

• item: 각 지역번호에 있는 아이템의 개수를 담는 배열로, 0, 5, 7, 8, 2, 3 이 담긴다.
• check: djikstra 함수에서 현재 살펴보는 정점이 시작 정점과 최단 거리를 갖는지 여부를 체크한다.
• distance: djikstra 함수에서 시작정점에서 현재 살펴보는 정점까지의 최단 거리를 담는다.

djikstra 함수

1.  시작 지역으로부터 모든 지역까지의 최단 거리를 distance[] 배열에 채운다. (while문에 해당)
2.  distance가 수색 범위 이하인 지역의 item만 itemTotal에 더한다. (while문 뒤, for문에 해당)

start가 1인 경우부터 areaCnt인 경우까지 총 areaCnt번 호출된다 !

for(int i=1; i<= areaCnt; i++) {
	maxNum = Math.max(maxNum, djikstra(i));
}

반환된 itemTotal 중 가장 큰 값이 답이 된다. (maxNum)

• itemTotal => 획득할 수 있는 아이템 갯수

private static int djikstra(int start) {
		int itemTotal =0;
		Arrays.fill(distance, Integer.MAX_VALUE); // 제일 최단 거리로 갱신하기 위해 큰값으로 초기화
		Arrays.fill(check, false); // 중복 여부 초기화
		
		PriorityQueue<Vertex> queue = new PriorityQueue<Vertex>();
		queue.offer(new Vertex(start, 0)); // 1. 시작 정점과, 자신과의 거리는 0이므로 0을 offer
		distance[start] = 0; // 자기 자신은 거리가 0
		
		while(!queue.isEmpty()) { // 시작 정점부터 모든 지역까지의 거리가 최단 거리로 채워질때까지!
			Vertex current = queue.poll(); // 2. 가장 작은 dis를 가진 Vertex가 poll된다. (PriorityQueue)
			int no = current.no; // 살펴볼 지역의 no (이하, 자기 자신)
			
			if(check[no]) continue; // 이미 최단거리가 확정됐으면 continue
			check[no] = true; // 가장 작은 dis를 가진 Vertex이므로 시작정점으로부터 최단 거리 확정
            // true가 됐다는 것은 start부터 자신까지의 거리인 distance[no]가 최단 거리로 확정됐다는 것을 의미
			
			for(Vertex vertex: graph[no]) { // 3. 자신은 확정이 됐고, 자신과 연결된 모든 지역 정보(Vertex)를 가져온다.
            // 4. 아직 살펴보지 않았고
            // && 기존에 저장되어 있는 시작 정점과의 거리보다 자기자신(no)를 경유해서 가는 경우가 더 작은 거리이면!
				if(!check[vertex.no] && distance[vertex.no] > distance[no] + vertex.dis) { 
					distance[vertex.no] = distance[no]+ vertex.dis; // 더 작은 거리로 갱신한다.
					// 갱신된 정보를 PriorityQueue에 담는다.
                    // start - no - vertex.no <= 이 상태를 담는 것!
                    queue.offer(new Vertex(vertex.no, distance[vertex.no]));
				}
			}
		}
		
		// 5. while문이 끝나면 distance에는 시작정점으로부터 가장 가까운 거리가 담겨있다.
		for(int i=1; i<=areaCnt; i++) {
			if(distance[i] <= areaLimit) { // 탐색 범위 이하이면
				itemTotal+= item[i]; // 아이템 get!
			}
		}
		return itemTotal;
	}

참고: queue에 offer 된 후, while문 초반에 (PriorityQueue) queue.poll 된다는 것은 자신이 시작 정점과 가장 가까운 거리를 가지고 있다는 것을 의미하기 때문에 check[no]를 true 로 바꿔 다음번에 자신과 시작 정점까지의 거리를 다른 값으로 갱신할 일이 없도록한다.

플로이드 마샬 알고리즘으로 푸는게 정석이라고 한다.

아직 플로이드 마샬을 안배워서 다익스트라로 풀었다! 내 풀이를 보고 다른 사람들의 이해에 도움이 됐으면 좋겠다.. 너무 어렵다