[SWEA | Java] 1249번 보급로

문제

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

SW Expert Academy

티어

소요 시간

12분

분류

bfs

다익스트라

코드

BFS

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

public class Solution {

    static int n;
    static int[][] map;

    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, -1, 0, 1};

    public static class Restore {
        int y, x;
        int money;

        public Restore(int y, int x, int money) {
            this.y = y;
            this.x = x;
            this.money = money;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int t = Integer.parseInt(br.readLine());
        for (int test = 1; test <= t; test++) {
            n = Integer.parseInt(br.readLine());
            map = new int[n][n];
            for (int i = 0; i < n; i++) {
                String line = br.readLine();
                for (int j = 0; j < n; j++) {
                    map[i][j] = line.charAt(j) - '0';
                }
            }

            System.out.println("#" + test + " " + bfs());
        }
    }

    private static int bfs() {
        PriorityQueue<Restore> queue = new PriorityQueue<>(Comparator.comparing(o -> o.money));
        queue.add(new Restore(0, 0, 0));
        boolean[][] visited = new boolean[n][n];

        while (!queue.isEmpty()) {
            Restore poll = queue.poll();
            int y = poll.y;
            int x = poll.x;
            int money = poll.money;

            if (y == n - 1 && x == n - 1) return money;

            if (!visited[y][x]) {
                visited[y][x] = true;
                for (int i = 0; i < 4; i++) {
                    int nextY = y + dy[i];
                    int nextX = x + dx[i];

                    if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < n && !visited[nextY][nextX]) {
                        queue.add(new Restore(nextY, nextX, money + map[nextY][nextX]));
                    }
                }
            }
        }
        return -1;
    }
}

BFS + 다익스트라

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Solution {

    static int n;
    static int[][] map;

    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, -1, 0, 1};

    public static class Restore {
        int y, x;
        int money;

        public Restore(int y, int x, int money) {
            this.y = y;
            this.x = x;
            this.money = money;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int t = Integer.parseInt(br.readLine());
        for (int test = 1; test <= t; test++) {
            st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            map = new int[n][n];
            for (int i = 0; i < n; i++) {
                st = new StringTokenizer(br.readLine());

                String line = st.nextToken();
                for (int j = 0; j < n; j++) {
                    map[i][j] = line.charAt(j) - '0';
                }
            }

            System.out.println("#" + test + " " + bfs());
        }
    }

    private static int bfs() {
        PriorityQueue<Restore> queue = new PriorityQueue<>(Comparator.comparing(o -> o.money));
        queue.add(new Restore(0, 0, 0));
        int[][] dist = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dist[i], Integer.MAX_VALUE);
        }

        while (!queue.isEmpty()) {
            Restore poll = queue.poll();
            int y = poll.y;
            int x = poll.x;
            int money = poll.money;

            if (money > dist[y][x]) continue;

            for (int i = 0; i < 4; i++) {
                int nextY = y + dy[i];
                int nextX = x + dx[i];

                if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < n) {
                    int nextMoney = money + map[nextY][nextX];
                    if (nextMoney < dist[nextY][nextX]) {
                        dist[nextY][nextX] = nextMoney;
                        queue.add(new Restore(nextY, nextX, nextMoney));
                    }
                }
            }
        }
        return dist[n - 1][n - 1];
    }
}

코드 설명

처음에는 bfs와 visited 배열을 이용했는데 다익스트라를 사용하는 색다른 풀이법을 보게 되었다.

하지만 아직 bfs와 visited를 이용하는 것이 손에 익숙하다.