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

문제

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

해결 방법

다익스트라 알고리즘을 활용하는 다른 문제 입니다.

다익스트라 알고리즘은 A에서 B로 시작점과 끝점이 문제에 주어져있고,

계산해야하는 값(거리나 비용 등)이 음수가 아닐 때 사용할 수 있습니다.

 

코드는 다른 다익스트라 알고리즘 문제와 비슷합니다.

 

코드

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

public class Main {
	static int dx[] = {0, 0, 1, -1};
	static int dy[] = {1, -1, 0, 0};
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		int cnt = 1; // 몇 번째 케이스인지 표시용
		
		while (true) {
			int N = Integer.parseInt(br.readLine());
			if (N == 0) break;
			
			int cave[][] = new int[N][N];
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				for (int j = 0; j < N; j++) {
					cave[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
			int money[][] = new int[N][N];
			for (int i = 0; i < N; i++) {
				Arrays.fill(money[i], Integer.MAX_VALUE);
				// 최댓값으로 전체 초기화
			}
			money[0][0] = cave[0][0];
			// 시작지점 초기화
			
			PriorityQueue<Node> q = new PriorityQueue<>();
			q.offer(new Node(0, 0, money[0][0]));
			
			while (!q.isEmpty()) {
				Node node = q.poll();
				if (node.x == N - 1 && node.y == N -1) {
					sb.append("Problem " + cnt + ": " + node.cost + "\n");
					cnt++;
					// 다익스트라에서는 가장 먼저 목적지에 도착한 값이 최소
					break;
				}
				
				for (int i = 0; i < 4; i++) {
					int newX = node.x + dx[i];
					int newY = node.y + dy[i];
					
					if (newX >= 0 && newY >= 0 && newX < N && newY < N) {
						if (money[newX][newY] > money[node.x][node.y] + cave[newX][newY]) {
							money[newX][newY] = money[node.x][node.y] + cave[newX][newY];
							q.offer(new Node(newX, newY, money[newX][newY]));
						}
					}
				}
			}
		}
		System.out.println(sb);
	}
}

class Node implements Comparable<Node>{
	int x;
	int y;
	int cost;
	
	Node (int x, int y, int cost) {
		this.x = x;
		this.y = y;
		this.cost = cost;
	}

	@Override
	public int compareTo(Node o) {
		// TODO Auto-generated method stub
		return cost - o.cost;
	}
}