[JAVA] 1249번 보급로

[JAVA] 1249번 보급로

문제

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

풀이

4방탐색 bfs 알고리즘에 우선순위 큐를 사용해 복구 시간이 가장 짧은 경로를 구하여 풀이하였다.

import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.PriorityQueue; import java.util.Queue; class Node implements Comparable{ int x; int y; int val; Node(int x, int y, int val) { this.x = x; this.y = y; this.val = val; } // 우선순위 큐 비교 @Override public int compareTo(Node n) { return this.val - n.val; } } public class SWEA1249_보급로 { static int N; static int arr[][]; static int depth[][]; static final int MAX = Integer.MAX_VALUE; static Queue q; static int result; static int dx[] = {-1, 1, 0, 0}; static int dy[] = {0, 0, -1, 1}; public static void solve() { while(!q.isEmpty()) { Node v = q.poll(); int x = v.x; int y = v.y; int val = v.val; // 도착지점 if (x == N - 1 && y == N - 1) { if (result > val) result = val; break; } // 상하좌우 이동 for (int i = 0; i < 4; i++) { int xx = x + dx[i]; int yy = y + dy[i]; if (xx < 0 || xx >= N || yy < 0 || yy >= N) continue; // 가중치 저장 if (depth[xx][yy] > arr[xx][yy] + val) { depth[xx][yy] = arr[xx][yy] + val; q.add(new Node(xx, yy, depth[xx][yy])); } } } } public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int T = Integer.parseInt(br.readLine()); for (int tc = 1; tc <= T; tc++) { N = Integer.parseInt(br.readLine()); arr = new int[N][N]; depth = new int[N][N]; q = new PriorityQueue<>(); // 우선순위 큐 result = MAX; for (int i = 0; i < N; i++) { String str = br.readLine(); for (int j = 0; j < N; j++) { arr[i][j] = str.charAt(j) - '0'; } Arrays.fill(depth[i], MAX); // max 값으로 초기화 } // 시작지점 depth[0][0] = arr[0][0]; q.add(new Node(0, 0, arr[0][0])); solve(); System.out.println("#" + tc + " " + result); } } }

from http://pekahblog.tistory.com/158 by ccl(S) rewrite - 2021-09-22 06:01:54