[알고리즘] Java / SWEA / 보급로 / 1249

[알고리즘] Java / SWEA / 보급로 / 1249

문제

문제 링크

접근 방식

다익스트라 알고리즘으로 (0,0) 위치에서 (N-1,N-1) 위치의 최단거리를 구한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;

public class Solution_1249_정현명 {

	public static class Vertex implements Comparable<Vertex>{
		int x;
		int y;
		int weight;
		
		Vertex(int x, int y, int weight){
			super();
			this.x = x;
			this.y = y;
			this.weight = weight;
		}

		@Override
		public int compareTo(Vertex o) {
			return this.weight - o.weight;
		}
	}
	
	static int N;
	static int[][] deltas = {{-1,0},{0,1},{1,0},{0,-1}};
	static int[][] map;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		
		StringBuilder sb = new StringBuilder();
		
		for(int tc=1;tc<=T;tc++) {
			N = Integer.parseInt(br.readLine());
			map = new int[N][N];
			
			for(int i=0;i<N;i++) {
				String line = br.readLine();
				for(int j=0;j<N;j++) {
					map[i][j] = line.charAt(j) - '0';
				}
			}
			
			sb.append("#"+tc+" "+dijkstra()+"\n");
		}
		System.out.print(sb);
	}
	
	
	
	static int dijkstra() {
		
		int distance[][] = new int[N][N];
		for(int i=0;i<N;i++) {
			Arrays.fill(distance[i], Integer.MAX_VALUE);			
		}
		
		
		distance[0][0] = 0;
		
		PriorityQueue<Vertex> pq = new PriorityQueue<>();
		pq.offer(new Vertex(0, 0, 0));
		
		while(!pq.isEmpty()) {
			
			Vertex v = pq.poll();
			
			for(int i=0;i<4;i++) {
				int nextX = v.x + deltas[i][0];
				int nextY = v.y + deltas[i][1];
				if(nextX<0||nextX>=N||nextY<0||nextY>=N) continue;
				if(distance[nextX][nextY] > distance[v.x][v.y]+ map[nextX][nextY]) {
					distance[nextX][nextY] = distance[v.x][v.y]+ map[nextX][nextY];
					pq.offer(new Vertex(nextX,nextY,distance[nextX][nextY]));
				}
			}
		}
		
		return distance[N-1][N-1];
	}
}