[SWEA] 1249. 보급로 D4 - Dijkstra

[SWEA] 1249. 보급로 D4 - Dijkstra

제출일 : 2019-10-07

문제 풀이 시간 : 30M

난이도 : ★★★

Problem

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

Input

가장 첫 줄은 전체 테스트케이스의 수이다.

각 테스트 케이스마다 지도의 크기(N x N)가 주어진다. 지도의 크기는 최대 100 x 100이다.

그 다음줄 부터 지도의 크기만큼 2차원 배열 형태의 지도 정보가 주어진다.

Output

각 테스트 케이스의 답을 순서대로 출력하며, 각 케이스마다 줄의 시작에 “#C”를 출력하여야 한다.

이때 C는 케이스의 번호이다.

같은 줄에 빈 칸을 하나 두고, 주어진 입력에서 출발지에서 도착지까지 가는 경로 중에 복구 작업에 드는 시간이 가장 작은 경로의 복구 시간을 출력하시오.

Example

input

10
4
0100
1110
1011
1010
6
011001
010100
010011
101001
010101
111010
8
. . .

output

#1 2
#2 2
. . .

Solution & Inpression

BFS로 이미 방문햇더라도 지금까지 계산한 값이 더작으면 queue에 담았습니다. >> 풀고나서 보니 다익스트라 알고리즘을 구현한것이었다.

code 1은 처음으로 구현한 풀이 방법이고

시간을 줄이기 위해 우선순위 큐를 사용하여 code 2를 작성하였다.

Code 1

언어 : JAVA

메모리 : 112,060 kb

실행시간 : 776 ms

import java.io.*;
import java.util.*;

public class Solution {
    static int N;
    static char[][] map;
    static int[][] mem;
    static int[] dr = { -1, 1, 0, 0 };
    static int[] dc = { 0, 0, -1, 1 };

    public static void main(String[] args) throws Exception {
        //System.setIn(new FileInputStream("res/D4_1249_보급로.txt"));

        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();

        for (int tc = 1; tc <= T; tc++) {
            N = sc.nextInt();
            map = new char[N][];
            mem = new int[N][N];

            for (int i = 0; i < N; i++) {
                map[i] = sc.next().toCharArray();
                Arrays.fill(mem[i], Integer.MAX_VALUE / 2);
            }

            Queue<int[]> q = new LinkedList<>();
            // 출발 = 0,0
            q.offer(new int[] { 0, 0, 0 });
            mem[0][0] = 0;
            while (!q.isEmpty()) {
                int[] tmp = q.poll();

                for (int k = 0; k < 4; k++) {
                    int r = tmp[0] + dr[k];
                    int c = tmp[1] + dc[k];
                    if (range(r, c)) {
                        int time = tmp[2] + Integer.parseInt("" + map[r][c]);
                        if (mem[r][c] > time) {
                            mem[r][c] = time;
                            q.offer(new int[] { r, c, mem[r][c] });
                        }
                    }
                }
            }
            System.out.println("#" + tc + " " + mem[N-1][N-1]);
        }
        sc.close();
    }

    private static boolean range(int r, int c) {
        if (0 <= r && r < N && 0 <= c && c < N)
            return true;
        return false;
    }
}

Code 2

언어 : JAVA

메모리 : 53,140 kb

실행시간 : 219 ms

import java.io.*;
import java.util.*;

public class Solution {
    static int N;
    static char[][] map;
    static int[][] mem;
    static int[] dr = { -1, 1, 0, 0 };
    static int[] dc = { 0, 0, -1, 1 };

    public static void main(String[] args) throws Exception {
        //System.setIn(new FileInputStream("res/D4_1249_보급로.txt"));

        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();

        for (int tc = 1; tc <= T; tc++) {
            N = sc.nextInt();
            map = new char[N][];
            mem = new int[N][N];

            for (int i = 0; i < N; i++) {
                map[i] = sc.next().toCharArray();
                Arrays.fill(mem[i], Integer.MAX_VALUE / 2);
            }

            PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    return Integer.compare(o1[2], o2[2]);
                }
            });
            // 출발 = 0,0
            pq.offer(new int[] { 0, 0, 0 });
            mem[0][0] = 0;
            while (!pq.isEmpty()) {
                int[] tmp = pq.poll();

                for (int k = 0; k < 4; k++) {
                    int r = tmp[0] + dr[k];
                    int c = tmp[1] + dc[k];
                    if (range(r, c)) {
                        int time = tmp[2] + Integer.parseInt("" + map[r][c]);
                        if (mem[r][c] > time) {
                            mem[r][c] = time;
                            pq.offer(new int[] { r, c, mem[r][c] });
                        }
                    }
                }
            }
            System.out.println("#" + tc + " " + mem[N-1][N-1]);
        }
        sc.close();
    }

    private static boolean range(int r, int c) {
        if (0 <= r && r < N && 0 <= c && c < N)
            return true;
        return false;
    }
}