[BOJ 4485] 녹색 옷 입은 애가 젤다지? (Java)

https://www.acmicpc.net/problem/4485

4485번: 녹색 옷 입은 애가 젤다지?

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

public class Main_BOJ_4485 {
	static class Node implements Comparable<Node>{
		int r, c, cost;
		public Node(int r, int c, int cost) {
			super();
			this.r = r;
			this.c = c;
			this.cost = cost;
		}
		@Override
		public int compareTo(Node o) {
			return this.cost-o.cost;
		}	
	}
	static int[] dr= {-1,1,0,0};
	static int[] dc= {0,0,-1,1};
	static int N;
	static int[][] map;
	static int[][] dist;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=null;
		int problem=1;
		while (true) {
			N=Integer.parseInt(br.readLine());
			if (N==0) break;
			map=new int[N][N];
			dist=new int[N][N];
			for (int i=0; i<N; i++) {
				st=new StringTokenizer(br.readLine());
				for (int j = 0; j < N; j++) {
					map[i][j]=Integer.parseInt(st.nextToken());
					dist[i][j]=Integer.MAX_VALUE;
				}
			}
			StringBuilder sb=new StringBuilder("Problem ");
			sb.append(problem); sb.append(": "+bfs());
			System.out.println(sb.toString());
			problem++;
		
		}
	}
	private static int bfs() {
		PriorityQueue<Node> q=new PriorityQueue<>();
		q.add(new Node(0,0,map[0][0]));
		dist[0][0]=map[0][0];
		while (!q.isEmpty()) {
			Node curr=q.poll();
			int r=curr.r;
			int c=curr.c;
			int cost=curr.cost;
			for (int i=0; i<4; i++) {
				int nr=r+dr[i];
				int nc=c+dc[i];
				if (nr<0 || nc<0 || nr>=N || nc>=N) continue;
				if (dist[nr][nc]>cost+map[nr][nc]) {
					dist[nr][nc]=cost+map[nr][nc];
					q.add(new Node(nr, nc, dist[nr][nc]));
				}
			}
		}
		return dist[N-1][N-1];
	}

}

다익스트라 느낌의 BFS 문제.

 

주변 4방향을 탐색해가면서 기존 거리보다 작은 거리로 도착이 가능할 경우, 그 값을 갱신해주고 그 노드를 탐색 대상으로 집어넣는다.