[알고리즘][X] 녹색 옷 입은 애가 젤다지?

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 {
	static int[][] map;
	static int[][] dist_map;
	static boolean[][] visited;
	static int N;
	static int[] dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};
	static StringBuilder sb = new StringBuilder();
	static class Node implements Comparable<Node>{
		int x;
		int y;
		int distance;
		public Node(int x, int y, int distance) {
			super();
			this.x = x;
			this.y = y;
			this.distance = distance;
		}
		
		@Override
		public String toString() {
			return "Node [x=" + x + ", y=" + y + ", distance=" + distance + "]";
		}

		@Override
		public int compareTo(Node o) {
			return distance - o.distance;
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int cnt = 0;
		while (true) {
			cnt++;
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			if (N == 0) {
				break;
			}
			map = 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_map = new int[N][N];
			visited = new boolean[N][N];
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					dist_map[i][j] = Integer.MAX_VALUE;
				}
			}
			dijkstra(0, 0);
			sb.append("Problem ").append(cnt).append(": ").append(dist_map[N-1][N-1]).append("\n");
		}
		System.out.println(sb);
		
	}
	private static void dijkstra(int x, int y) {
		PriorityQueue<Node> pq = new PriorityQueue<>();
		dist_map[x][y] = map[x][y];
		pq.add(new Node(x, y, map[x][y]));
		
		while (!pq.isEmpty()) {
			Node node = pq.poll();
			x = node.x;
			y = node.y;
			if (visited[x][y]) {
				continue;
			}
			visited[x][y] = true;
			for (int i = 0; i < 4; i++) {
				
				int nx = x + dx[i];
				int ny = y + dy[i];
				
				if (0 <= nx && nx < N && 0 <= ny && ny < N && !visited[nx][ny]) {
					if (dist_map[nx][ny] > dist_map[x][y] + map[nx][ny]) {
						dist_map[nx][ny] = dist_map[x][y] + map[nx][ny];
						pq.add(new Node(nx, ny, dist_map[nx][ny]));
					}
				}
			}
		}
		
	}
//	private static int dfs(int x, int y, int sum) {
//		if (x == N-1 && y == N-1) {
//			return map[N-1][N-1];
//		}
//		int mn = Integer.MAX_VALUE;
//		for (int i = 0; i < 4; i++) {
//			int nx = x + dx[i];
//			int ny = y + dy[i];
//			
//			if (0 <= nx && nx < N && 0 <= ny && ny < N) {
//				if (new_map[nx][ny] > sum + map[nx][ny]) {
//					new_map[nx][ny] = sum + map[nx][ny];
//					mn = Math.min(mn, dfs(nx, ny, sum + map[nx][ny]));
//				}
//			}
//		}
//		
//		dp_map[x][y] = map[x][y] + mn; 
//		return map[x][y] + mn;
//	}
}

나의 풀이

- 가중치가 양수라면 다익스트라를 떠올려보자

- dfs로 구하게 되면 시간초과가 난다. 너무 느리다!!!!!!

- 다익스트라 함수 안에서 x가 인자로 주어져서 node.x를 정의했는데 정작 사용하는 건 x를 사용했다. 음... 이런 경우를 없애기 위해서 아예 변수를 다르게 정의하자. 예를 들어, a, b와 x, y를 쓴다는 식으로