1249_보급로

사용 알고리즘: 다익스트라? (dp + bfs)

사용 언어: java

 

package week31_32;

import java.util.*;
import java.io.*;
public class Solution_swea_1249_보급로 {
	static int dp[][], N, map[][];
	static int[] dx = {1,0,-1,0}; //하우상좌
	static int[] dy = {0,1,0,-1};

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for (int t = 1; t <= T; t++) {
//			answer = N*N*9;
			N = Integer.parseInt(br.readLine());
			map = new int[N][N];
			dp = new int[N][N];
			for (int i = 0; i < N; i++) {
				String s = br.readLine();
				for (int j = 0; j < N; j++) {
					map[i][j] = s.charAt(j) - '0';
				}
			}
			
			for (int i = 0; i < N; i++) {
				Arrays.fill(dp[i], Integer.MAX_VALUE);
			}
			solution();
			
			System.out.println("#"+t+" "+dp[N-1][N-1]);
		}
	}

	private static void  solution() {
		Queue<int[]> pq = new PriorityQueue<>((a, b) -> a[2]-b[2]);
		pq.add(new int[] {0,0, 0});
		
		while(!pq.isEmpty()) {
			int[] cur = pq.poll();
			
//			if(cur[0]==N-1 && cur[1]==N-1) {
//				return cur[2];
//			}
			
			for (int d = 0; d < 4; d++) {
				int nx = cur[0] + dx[d];
				int ny = cur[1] + dy[d];
				
				if(isInTheMap(nx,ny) && dp[nx][ny] > cur[2]+map[nx][ny]) {
					dp[nx][ny] = cur[2]+map[nx][ny];
					pq.add(new int[] {nx, ny, cur[2]+map[nx][ny]});
				}
			}
		}
		
//		return -1;
	}

	private static boolean isInTheMap(int nx, int ny) {
		if(nx<0 || nx>=N || ny<0 || ny>=N)
			return false;
		return true;
	}

}

 

 

무난하게 풀렸다.