[JAVA] SWEA (D4) 1249. 보급로

링크

링크

---

문제 설명

정답률 76.01%
출발지에서 도착지까지 가는 경로 중에 복구 작업에 드는 시간이 가장 작은 경로의 복구 시간을 출력하시오.

---

입력 예제

4
0100
1110
1011
1010

---

출력 예제

2

---

풀이

출발지에서 도착지까지 최단 경로를 구해야 한다. 복구 작업에 드는 시간은 가중치로 볼 수 있다. 시작점과 다른 노드와의 최단 경로는 다익스트라 알고리즘으로 응용하여 해결할 수 있다.

출발지에서 시작해서 도착지까지 탐색을 하는 것은 BFS와 동일하나 우선순위 큐를 이용해서 가중치가 작은 노드부터 탐색한다.

//가중치를 기준으로 정렬
PriorityQueue<int[]> queue = new PriorityQueue<>(comparingInt(o -> map[o[0]][o[1]]));

나머지는 BFS와 동일하게 진행한다. 방문하지 않은 노드일 경우 방문한 뒤 가중치를 누적해간다.

if (!visited[nextR][nextC]) {
    visited[nextR][nextC] = true;
    map[nextR][nextC] += map[curR][curC];
    queue.add(new int[]{nextR, nextC});
}

전체 코드

import static java.util.Comparator.comparingInt;

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

class SWEA {

    static boolean[][] visited;
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};
    static int[][] map;
    static int N;

    public static void main(String[] args) throws IOException {

        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());

        for (int testCase = 1; testCase <= T; testCase++) {

            N = Integer.parseInt(br.readLine());  //지도의 크기
            visited = new boolean[N][N];
            map = new int[N][N];
            //입력값 초기화
            for (int i = 0; i < N; i++) {
                map[i] = Arrays.stream(br.readLine().split(""))
                        .mapToInt(Integer::parseInt)
                        .toArray();
            }

            bfs();

            System.out.println("#" + testCase + " " + map[N - 1][N - 1]);
        }
    }

    static void bfs() {
        PriorityQueue<int[]> queue = new PriorityQueue<>(comparingInt(o -> map[o[0]][o[1]]));
        queue.add(new int[]{0, 0});
        visited[0][0] = true;

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int curR = cur[0];
            int curC = cur[1];

            for (int i = 0; i < 4; i++) {
                int nextR = curR + dr[i];
                int nextC = curC + dc[i];

                if (nextR < 0 || nextR >= N | nextC < 0 || nextC >= N) {
                    continue;
                }

                if (!visited[nextR][nextC]) {
                    visited[nextR][nextC] = true;
                    map[nextR][nextC] += map[curR][curC];
                    queue.add(new int[]{nextR, nextC});
                }
            }
        }
    }

}