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

1.  문제 링크

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

2.  문제

요약

• 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)입니다.
• '도둑루피'라 불리는 검정색 루피가 존재하는데, 이를 획득하면 오히려 소지한 루피가 감소하게 됩니다.
• 링크는 지금 도둑루피만 가득한 N x N 크기의 동굴의 제일 왼쪽 위인 [0][0]번 칸에 있고 동굴의 반대편 출구, 즉 제일 오른쪽 아래 칸인 [N - 1][N - 1]칸까지 이동해야 합니다.
• 동굴의 각 칸마다 도둑루피가 있는데, 이 칸을 지나면 해당 도둑루피의 크기만큼 소지금을 잃게 됩니다.
• 링크는 잃는 금액을 최소로 하여 동굴 건너편까지 이동해야 하며, 한 번에 상하좌우 인접한 곳으로 한 칸씩 이동할 수 있습니다.
• 링크가 잃을 수 밖에 없는 최소 금액이 얼마인지 구하는 문제입니다.
• 입력: 입력은 여러 개의 테스트 케이스로 이루어져 있고, 각 테스트 케이스의 첫 번째 줄에는 2보다 크거나 같고 125보다 작거나 같은 동굴의 크기를 나타내는 정수 N이 주어지고 두 번째 줄부터 N개의 줄에 걸쳐 동굴의 각 칸에 있는 도둑루피의 크기가 주어집니다. N = 0인 입력이 주어지면 전체 입력이 종료된다.
  • 도둑루피의 크기가 k면 해당 칸을 지나면 k루피를 잃는다는 뜻이고 k는 0 이상 9 이하인 정수입니다.
• 출력: 각 테스트 케이스마다 한 줄에 걸쳐 정답을 형식에 맞게 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int N, min;
	static int[][] map;
	static int[] dx = {-1, 0, 1, 0}, dy = {0, -1, 0, 1};
	static void input() {
		Reader scanner = new Reader();
		int cnt = 1;
		while(true) {
			N = scanner.nextInt();
			if(N == 0) break;
			map = new int[N][N];
			for(int row = 0; row < N; row++) {
				for(int col = 0; col < N; col++) map[row][col] = scanner.nextInt();
			}
			min = Integer.MAX_VALUE;
			solution(cnt);
			cnt++;
		}
	}
	
	static void solution(int cnt) {
		bfs();
		sb.append("Problem ").append(cnt).append(": ").append(min).append('\n');
	}
	
	static void bfs() {
		Queue<int[]> loc = new LinkedList<int[]>();
		int[][] cost = new int[N][N];
		for(int row = 0; row < N; row++) Arrays.fill(cost[row], Integer.MAX_VALUE);
		loc.offer(new int[] {0, 0});
		cost[0][0] = map[0][0];
		while(!loc.isEmpty()) {
			int[] curLoc = loc.poll();
			if(curLoc[0] == N - 1 && curLoc[1] == N - 1) {
				min = Math.min(min, cost[curLoc[0]][curLoc[1]]);
			}
			for(int dir = 0; dir < 4; dir++) {
				int cx = curLoc[0] + dx[dir];
				int cy = curLoc[1] + dy[dir];
				if(cx >= 0 && cx < N && cy >= 0 && cy < N) {
					if(cost[cx][cy] > cost[curLoc[0]][curLoc[1]] + map[cx][cy]) {
						cost[cx][cy] = cost[curLoc[0]][curLoc[1]] + map[cx][cy];
						loc.offer(new int[] {cx, cy});
					}
				}
			}
		}
	}
	
	public static void main(String[] args) {
		input();
		System.out.println(sb);
	}
	
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch(IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
	}
}