SWEA - 보급로 JAVA

백준4485 - 녹색옷을 입은 젤다와 99프로 일치하는 문제다 

한 노드에서 다른 한노드로의 최소경로를 구하는데, 가중치가 다른 상황이므로 

다익스트라 알고리즘을 적용하면 바로 풀린다. 

 

시작은 (0,0) 도착지는 (size-1, size-1) 이다. 

 

 

package a0407;

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

public class SWEA보급로 {

	static int size;
	static int[][] arr; 
	static int[][] sumarr;
	
	static class node implements Comparable<node>{
		int xidx;
		int yidx;
		int weight;
		
		node(int xidx, int yidx, int weight){
			this.xidx = xidx;
			this.yidx = yidx;
			this.weight = weight;
		}

		@Override
		public int compareTo(node o) {
			return this.weight-o.weight;
		}
	}
	
	static boolean check(int i, int j) {
		if(0<=i&&i<size && 0<=j&&j<size)return true;
		return false;
	}
	
	public static void main(String[] args) throws Exception{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int tc = Integer.parseInt(br.readLine());
		
		for(int t=1; t<=tc; t++) {
			
			size = Integer.parseInt(br.readLine());
			arr = new int[size][size];
			sumarr = new int[size][size];
			
			for(int i=0; i<size; i++) {
				String st = br.readLine();
				for(int j=0; j<size; j++) {
					arr[i][j] = st.charAt(j)-'0';
					sumarr[i][j] = Integer.MAX_VALUE;
				}
			}
			sumarr[0][0] = arr[0][0];
			System.out.println("#"+t+" "+daic());
			
		}
		
	}
	
	static int[] di = {-1, 0, 1, 0};
	static int[] dj = {0, 1, 0, -1};
	
	static int daic() {
		PriorityQueue<node> pq = new PriorityQueue<>();
		pq.offer(new node(0,0,arr[0][0]));
		
		while(!pq.isEmpty()) {
			node now = pq.poll();
			int nowi = now.xidx;
			int nowj = now.yidx;
			
			for(int d=0; d<4; d++) {
				int ni = nowi+di[d];
				int nj = nowj+dj[d];
				
				if(check(ni,nj)) {
					if(sumarr[ni][nj] > sumarr[nowi][nowj]+arr[ni][nj]) {
						sumarr[ni][nj] = sumarr[nowi][nowj]+arr[ni][nj];
						pq.offer(new node(ni, nj, sumarr[ni][nj]));
					}
				}
			} 
		}
		return sumarr[size-1][size-1];
	}

}