[Java] 백준 4485번: 녹색 옷 입은 애가 젤다지?

[문제 바로 가기] - 녹색 옷 입은 애가 젤다지?

💡 접근 방식

다익스트라를 익힐 겸 풀어본 문제로 1년 전에 싸피에서 풀어봤던 문제다.

다익스트라에서 중요한 부분

1. 최소 합을 저장할 배열 sum을 Integer.MAX_VALUE로 초기화 해준다.
   이때 (0, 0)에서 시작하므로 sum[0][0]은 arr[0][0]로 초기화 한다.
2. PriorityQueue를 이용해서 지금까지 경로에서의 합을 기준으로 오름차순 정렬한다.
3. BFS를 돌면서 sum[X][Y] + arr[dx][dy]가 sum[dx][dy]보다 작을 경우 sum[dx][dy]를 갱신해준다. 그리고 갱신한 값을 Queue에 넣어준다.

다익스트라 문제를 더 풀어봐야겠다!

풀이

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int deltas[][] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
		
		int index = 1;
		while (true) {
			int N = Integer.parseInt(br.readLine());
			
			if (N == 0) break;
			
			int arr[][] = new int[N][N];
			int sum[][] = new int[N][N];
			
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < N; j++) {
					arr[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					sum[i][j] = Integer.MAX_VALUE;
				}
			}
			
			PriorityQueue<int []> queue = new PriorityQueue<>((o1, o2) -> o1[2] - o2[2]);
			queue.add(new int[] {0, 0, arr[0][0]});
			sum[0][0] = arr[0][0];
			
			while (!queue.isEmpty()) {
				int cur[] = queue.poll();
				int X = cur[0];
				int Y = cur[1];
				
				for (int i = 0; i < 4; i++) {
					int dx = X + deltas[i][0];
					int dy = Y + deltas[i][1];
					
					if (dx < 0 || dy < 0 || dx >= N || dy >= N) continue;
					
					if (sum[dx][dy] > sum[X][Y] + arr[dx][dy]) {
						sum[dx][dy] = sum[X][Y] + arr[dx][dy];
						queue.add(new int[] {dx, dy, sum[dx][dy]});
					}
				}				
			}
			
			System.out.println("Problem " + index++ + ": " + sum[N - 1][N - 1]);
		}
	}
}