[Java Algorithm] 녹색 옷 입은 애가 젤다지?

문제

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

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

 

내 문제 풀이

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

public class BOJ_4485 {

	static class Node implements Comparable<Node> {
		int x;
		int y;
		int w;

		public Node(int x, int y, int w) {
			this.x = x;
			this.y = y;
			this.w = w;
		}

		@Override
		public int compareTo(Node o) {
			return Integer.compare(this.w, o.w);
		}
	}

	static int n, idx;
	static int[][] map;
	static int[][] dis;
	static int[] dx = {0, 0, -1, 1};
	static int[] dy = {-1, 1, 0, 0};

	public static void Dijk() {
		PriorityQueue<Node> pq = new PriorityQueue<>();
		pq.add(new Node(0, 0, map[0][0])); // x, y, w
		dis[0][0] = map[0][0];

		while(!pq.isEmpty()) {
			Node now = pq.poll();
			int x = now.x;
			int y = now.y;
			int w = now.w;

			for(int i = 0; i < 4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];

				if(nx < 0 || ny < 0 || nx >= n || ny >= n || dis[nx][ny] <= map[nx][ny] + w) continue;

				dis[nx][ny] = map[nx][ny] + w;
				pq.add(new Node(nx, ny, dis[nx][ny]));
			}
		}
	}

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder out = new StringBuilder();

		while(true) {
			idx++;
			n = Integer.parseInt(in.readLine());
			if(n == 0) break;

			map = new int[n][n];
			dis = new int[n][n];
			for(int i = 0; i < n; i++) {
				st = new StringTokenizer(in.readLine());
				for(int j = 0; j < n; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
					dis[i][j] = Integer.MAX_VALUE;
				}
			}

			Dijk();
			out.append("Problem " + idx + ": " + dis[n-1][n-1] + "\n");
		}

		System.out.print(out);
	}
}

👉 다익스트라 문제

• Node 클래스를 만들고, 도둑루피의 값 w 기준 오름차순 정렬할 수 있도록 했다.
• 입력받는 동굴 정보를 map 2차원 배열에 저장했고,
  dis 배열은 map과 같은 크기로 하되 모든 칸을 MAX_VALUE로 채워주었다. (최솟값 갱신 위해)
• Dijk 메서드에서는 최솟 값을 가장 효율적으로 구할 수 있도록 PriorityQueue를 만들었고
  탐색 시작점으로 0, 0 좌표와 그에 해당하는 도둑루피 값을 pq에 넣어주었다.
• while은 보편적인 bfs 탐색과 같다.
  pq의 맨 앞에서 값을 하나 빼오고, 그 값을 토대로 상하좌우 탐색을 해주었다.
  dis[nx][ny] <= map[nx][ny] + w 이면 해당 경로로는 더이상 최솟값일 가능성이 없다는 뜻이므로,
  위의 경우를 제외하고는 dis 배열을 최솟값으로 초기화하고, pq에도 새로운 탐색 시작점을 추가했다.
• Dijk 메서드가 종료되면 dis 배열의 가장 마지막 칸에 저장된 값을 출력해주면 된다.

 

💡 피드백

• PriorityQueue를 사용하지 않아도 충분히 풀이가 가능하지만,
  사용하고 안하고의 차이가 거의 두 배 시간 차이가 나더라!!!!