[SW Expert 1249] 보급로 (Java)

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=4&contestProbId=AV15QRX6APsCFAYD&categoryId=AV15QRX6APsCFAYD&categoryType=CODE&problemTitle=&orderBy=INQUERY_COUNT&selectCodeLang=ALL&select-1=4&pageSize=10&pageIndex=1 

SW Expert Academy

 

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Solution {
	static int T, N;
	static String s;
	static int[] dr= {0,1,-1,0};
	static int[] dc= {1,0,0,-1};
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		T=sc.nextInt();
		for (int t=1; t<=T; t++) {
			N=sc.nextInt();
			int[][] board=new int[N][N];
			int[][] dist=new int[N][N];
			PriorityQueue<Node> q=new PriorityQueue<>();
			for (int i=0; i<N; i++) {
				s=sc.next();
				for (int j=0; j<N; j++) {
					board[i][j]=s.charAt(j)-'0';
				}
				Arrays.fill(dist[i], Integer.MAX_VALUE);
			}
			q.add(new Node(0,0,0));
			dist[0][0]=0;
			while (!q.isEmpty()) {
				Node now=q.poll();
				if (dist[now.r][now.c]<now.cost) {
					continue;
				}
				if (now.r==N-1 && now.c==N-1) {
					break;
				}
				for (int i=0; i<4; i++) {
					int nr=now.r+dr[i];
					int nc=now.c+dc[i];
					if (nr<0 || nc<0 || nr>=N || nc>=N)
						continue;
					if (now.cost+board[nr][nc]<dist[nr][nc]) {
						dist[nr][nc]=now.cost+board[nr][nc];
						q.add(new Node(nr,nc,dist[nr][nc]));
					}
				}
			}
			
			System.out.printf("#%d %d\n", t, dist[N-1][N-1]);
		}
	}
	public static class Node implements Comparable<Node>{
		int r;
		int c;
		int cost;
		Node(int r, int c, int cost){
			this.r=r;
			this.c=c;
			this.cost=cost;
		}
		@Override
		public int compareTo(Node o) {
			if (this.cost>o.cost) {
				return 1; 				//오름차순
			}
			else if (this.cost<o.cost) {
				return -1;
			}
			return 0;
		}
	}

}

다익스트라와 BFS를 이용한 문제.

 

출발지, 도착지 고정이고 최저 경로를 구하는 문제이므로 다익스트라이다.

다익스트라에서 인접 노드를 선택할 때 BFS 를 이용하는 것이 이문제의 포인트다.