[SWEA]1249: 보급로 D4(Java)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD 

SW Expert Academy

 

 

package SWEA;

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

public class Solution_1249 {
	static int map[][];
	static int N, res;
	static int[] dx = { -1, 1, 0, 0 };
	static int[] dy = { 0, 0, 1, -1 };

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());

		for (int t = 1; t < T + 1; t++) {
			N = Integer.parseInt(br.readLine());
			map = new int[N][N];

			for (int i = 0; i < N; i++) {
				String s = br.readLine();
				for (int j = 0; j < N; j++) {
					map[i][j] = s.charAt(j) - '0';
				}
			}
			res = 0;
			bfs();
			System.out.println("#" + t + " " + res);

		}
	}

	private static void bfs() {
		// 우선순위 큐 사용
		PriorityQueue<Node> que = new PriorityQueue<>();
		boolean visit[][] = new boolean[N][N];
		visit[0][0] = true;
		que.add(new Node(0, 0, map[0][0]));

		while (!que.isEmpty()) {
//			Iterator iterator = que.iterator();
//			while (iterator.hasNext())
//				System.out.println(iterator.next() + " ");
			Node node = que.poll();

			if (node.x == N - 1 && node.y == N - 1) {
				res = node.time;
				return;
			}

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

				// 첫 비교대상 초기화
				if (nx >= 0 && ny >= 0 && nx < N && ny < N && visit[ny][nx] != true) {
					// 시간 갱신해서 우선순위 큐에 넣음
					int totalTime = node.time + map[ny][nx];
					que.add(new Node(ny, nx, totalTime));
					visit[ny][nx] = true;

				}
			}
		}

	}

	static public class Node implements Comparable<Node> {
		int x, y, time;

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

		@Override
		// 복구시간이 작을수록 -> 오름차순 정렬
		public int compareTo(Node o) {
			return this.time - o.time;
		}

		@Override
		public String toString() {
			return "Node [x=" + x + ", y=" + y + ", time=" + time + "]";
		}

	}

}

bfs만 써서 풀라고 했는데 쉽게 될리가 읍지,,

우선순위 큐를 사용하거나 혹은 dp+bfs로 푸는 방법이 있는듯

나는 우선순위 큐를 사용해서 time이 적게 걸리는 순으로 오름차순 시킴