[문제] SWEA 1249번 보급로

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD&categoryId=AV15QRX6APsCFAYD&categoryType=CODE&problemTitle=1249&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

SW Expert Academy

내풀이

 

다익스트라 사용하기!

 

public class Solution {
	
	static int N, map[][], INF = Integer.MAX_VALUE;
	static int dr[] = {-1,1,0,0};
	static int dc[] = {0,0,-1,1};
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(in.readLine());
		StringBuilder sb = new StringBuilder();
		
		for(int tc= 1;tc<=T;tc++) {
			N = Integer.parseInt(in.readLine());	// 배열 크기
			// init map
			map = new int[N][N];
			for(int i=0;i<N;i++) {
				char[] ch = in.readLine().toCharArray();
				for(int j=0;j<N;j++) {
					map[i][j] = ch[j] - '0';
				}
			}
			
			int res = dijkstra(0,0);
			sb.append('#').append(tc).append(' ').append(res).append('\n');
		}
		System.out.println(sb);
	}

	static int dijkstra(int startR, int startC) {
		// r, c, d
		PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				// TODO Auto-generated method stub
				return o1[2]-o2[2];
			}
			
		});
		
		int[][] minDist = new int[N][N];
		boolean[][] visited = new boolean[N][N];
		
		for(int i=0;i<N;i++) {
			for(int j =0;j<N;j++) {
				minDist[i][j] = INF;
			}
		}
		minDist[startR][startC] = 0;
		pq.offer(new int[] {startR, startC, minDist[startR][startC]});
		while(true) {
			int[] curr = pq.poll();
			int minR = curr[0];
			int minC = curr[1];
			int min = curr[2];
			
			
			visited[minR][minC] = true;
			if(minR == N-1 && minC == N-1) return min;
			
			for(int d=0;d<4;d++) {
				int nr= minR + dr[d];
				int nc = minC + dc[d];
				if(nr>=0 && nr<N && nc>=0 && nc<N 
						&& !visited[nr][nc] && minDist[nr][nc] > min + map[nr][nc]) {
					minDist[nr][nc] = min + map[nr][nc];
					pq.offer(new int[] {nr, nc, minDist[nr][nc]});
				}
			}
		}
		
	}

}