백준 4485 - 녹색 옷 입은 애가 젤다지?

Java

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

문제

접근 방법

2차원 배열을 그래프라고 생각하고, [0, 0]에서 [n - 1][n - 1]으로 이동하는 최단 거리를 구하면 된다.

즉 다익스트라를 이용하여 최단 거리를 구하면 된다.

모든 정점끼리 상하좌우로 이어져있다고 생각하고, 다익스트라를 적용하면 해결 가능하다.

코드

import java.util.*;
import java.io.*;

public class Main {
	static int n, result;
	static int MAX_VALUE = 99999999;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
		StringTokenizer stk;
		StringBuilder sb = new StringBuilder();
		// 상 하 좌 우
		int[] dy = {-1, 1, 0, 0};
		int[] dx = {0, 0, -1, 1};
		int idx = 1;
		while(true) {
			n = stoi(br.readLine());
			
			if(n == 0)
				break;
			
			int[][] graph = new int[n][n];
			
			for(int i = 0; i < n; i++) {
				stk = new StringTokenizer(br.readLine());
				for(int j = 0; j < n; j++) {
					graph[i][j] = stoi(stk.nextToken());
				}
			}
			int size = (int)Math.pow(n, 2);
			int[] node = new int[size];
			boolean[] vis = new boolean[size];
			
			Arrays.fill(node, MAX_VALUE);
			
			int min, curN = 0, x, y, nx, ny, nextN;
			node[0] = graph[0][0];
			while(true) {
				// 다음 노드를 선택
				min = MAX_VALUE;
				for(int i = 0; i < size; i++) {
					if(node[i] < min && !vis[i]) {
						min = node[i];
						curN = i;
					}
				}
				// 더 이상 선택되는 노드가 없으면 종료
				if(min == MAX_VALUE)
					break;
				
				vis[curN] = true;
				// y,x 좌표로 변환
				y = curN / n;
				x = curN % n;
				// 현재 curN을 경유하여 상하좌우 이동했을 때 원래 좌표에 도달하는 비용보다 더 낮을 때
				for(int i = 0; i < 4; i++) {
					ny = y + dy[i];
					nx = x + dx[i];
					nextN = ny * n + nx;
					if(isIn(ny,nx) && !vis[nextN]) {
						if(node[nextN] > node[curN] + graph[ny][nx]) {
							node[nextN] = node[curN] + graph[ny][nx];
						}
					}
				}
			}
			sb.append("Problem " + idx + ": ").append(node[size - 1]).append("\n");
			idx++;
		}
    	System.out.print(sb.toString());
    	br.close();
	}
	static boolean isIn(int y, int x) {
		if(0 <= y && y < n && 0 <= x && x < n)
			return true;
		return false;
	}
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

개선할 점