[SWEA] 보급로 - JAVA(자바)

문제: https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&problemLevel=4&contestProbId=AV15QRX6APsCFAYD&categoryId=AV15QRX6APsCFAYD&categoryType=CODE&problemTitle=&orderBy=RECOMMEND_COUNT&selectCodeLang=ALL&select-1=4&pageSize=10&pageIndex=1

SW Expert Academy

 

풀이:

BFS를 구현할 때 Queue가 아닌 우선순위큐를 사용한다. 우선순위는 각 칸 까지 가는데 복구 시간이 작은게 높은 우선순위를 갖는다. 이렇게 되면 q.poll()을 호출할 때마다 적게 걸린 시간의 경로가 나와  결국 최다 경로를 찾을 수 있다.

 

코드:

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


class Solution
{
    static int n;
    static int[][] board;
    static boolean[][] isVisited;

    static int min;

    public static void main(String args[]) throws Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int testCase = Integer.parseInt(br.readLine());
        for (int t = 1; t <= testCase; t++) {
            n = Integer.parseInt(br.readLine());
            board = new int[n][n];
            isVisited = new boolean[n][n];
            min = Integer.MAX_VALUE;

            for (int i = 0; i < n; i++) {
                String line = br.readLine();
                for (int j = 0; j < n; j++) {
                    board[i][j] = line.charAt(j) - '0';
                }
            }
            bfs();
            sb.append("#").append(t).append(" ").append(min).append("\n");
        }
        System.out.println(sb);
    }

    static void bfs() {
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, -1, 0, 1};
        Queue<Point> q = new PriorityQueue<>(); // 시간이 덜 걸린 경로가 우선순위가 돼서 결국 최단 경로를 고려하게 된다.
        q.add(new Point(0, 0, 0));
        isVisited[0][0] = true;

        while (!q.isEmpty()) {
            Point cur = q.poll();
            if (cur.x == n - 1 && cur.y == n - 1) {
                min = Math.min(min, cur.time);
            }
            for (int i = 0; i < 4; i++) {
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];
                if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
                if(!isVisited[nx][ny]){
                    q.add(new Point(nx, ny, board[nx][ny] + cur.time));
                    isVisited[nx][ny] = true;
                }

            }
        }
    }
}

class Point implements Comparable<Point>{
    int x,y, time;

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

    @Override
    public int compareTo(Point o) {
        return this.time - o.time;
    }
}