[SWEA/Java] (SW Expert Academy) 1249 보급로

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

SW Expert Academy

해당 사이트의 문제는 로그인을 진행한 후 확인할 수 있습니다.

 

 

🔍 해결 과정

문제를 처음 봤을 때 언뜻 보면 평범하게 dfs를 활용하여 문제를 해결하면 되겠다 싶겠지만, dfs의 정의상 구조적으로 해결할 수가 없습니다.

dfs는 특정 시작점에서 목적지까지 도달하는데 거리상으로 걸리는 비용의 최솟값을 구하기 때문입니다.

 

이 문제는 보급로의 칸마다 걸리는 시간이 배치되어 있고, 목적지까지 도달하면서 보급로의 칸에 있는 시간을 누적하면서 보급로를 확보하기까지 걸리는 시간의 최솟값을 구해야 합니다. 즉, 다익스트라를 활용하여 문제를 해결해야 합니다.

 

과정 설명은 다음과 같습니다.

1️⃣ 특정 목적지까지 걸리는 시간 정보를 담을 정수형 일차원 배열 d를 만들어준다. (보급로 배열이 정사각형의 이차원 배열이므로 번호를 그에 맞게 매핑을 진행해줌)
2️⃣ 노드의 번호와 도로 복구에 걸리는 시간 정보를 담는 class Node를 만들어준다.
3️⃣ 노드 번호는 일차원 배열 d에 맞춰서 진행할 것이기에 그에 맞는 graph를 따로 만들어준다. (노드 번호도 d에 맞춰서 진행)
4️⃣ graph와 d, 우선순위 큐를 활용하여 다익스트라를 진행한다.
5️⃣ d에서 최종 목적지에 도달했을 때 걸리는 시간을 계산해준다.

 

저는 약간 어려운 방식으로 문제를 해결했지만, 시간 정보 d 테이블을 이차원으로 그대로 적용해 더 쉽게 문제를 해결할 수가 있습니다.

지도 정보가 2차원 배열 형태로 만들어져있기 때문에 각 지도의 칸을 하나의 노드로 본다면 노드별로 상하좌우로 연결되어 있기 때문에 이차원 배열 그대로 다익스트라를 진행하면서 상하좌우만 살펴보면서 거리 정보를 계산하면 되기 때문입니다.

 

---

✏️ 코드

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

class Node implements Comparable<Node> {
    private final int index;
    private final int time;

    public Node(int index, int time) {
        this.index = index;
        this.time = time;
    }

    public int getIndex() {
        return index;
    }

    public int getTime() {
        return time;
    }

    @Override
    public int compareTo(Node o) {
        return Integer.compare(time, o.time);
    }
}

public class Main {

    private static final int INF = (int) 1e9;

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        int t = Integer.parseInt(br.readLine());

        for (int tc = 1; tc <= t; ++tc) {
            sb.append("#").append(tc).append(" ");
            int n = Integer.parseInt(br.readLine());
            int[][] board = new int[n][n];

            for (int i = 0; i < n; ++i) {
                board[i] = Arrays.stream(br.readLine().split(""))
                        .mapToInt(Integer::parseInt)
                        .toArray();
            } // 보드 입력 완료

            // 다익스트라 진행
            int[] d = new int[n * n];
            Arrays.fill(d, INF);
            dijkstra(board, n, d, 0);

            sb.append(d[n * n - 1]).append("\n");
        }

        bw.write(sb.toString());
        bw.flush();
    }

    private static void dijkstra(int[][] board, int n, int[] d, final int start) {
        // 그래프를 만들어서 서로 연결짓기
        List<List<Node>> graph = makeGraph(board, n);
        Queue<Node> q = new PriorityQueue<>(); // 우선순위 큐를 활용하여 시간이 적은 순으로
        q.offer(new Node(start, 0));
        d[start] = 0;

        // 연결 지은 그래프를 기준으로 다익스트라 진행하기
        while (!q.isEmpty()) {
            Node cur = q.poll();
            int curIndex = cur.getIndex();
            int curTime = cur.getTime();
            int size = graph.get(curIndex).size();

            if (curTime > d[curIndex]) {
                continue;
            }

            for (int i = 0; i < size; ++i) {
                int nextIdx = graph.get(curIndex).get(i).getIndex();
                int nextTime = graph.get(curIndex).get(i).getTime();
                int cost = d[curIndex] + nextTime;
                if (cost >= d[nextIdx]) {
                    continue;
                }

                q.offer(new Node(nextIdx, cost));
                d[nextIdx] = cost;
            }
        }
    }

    private static List<List<Node>> makeGraph(int[][] board, int n) {
        List<List<Node>> graph = new ArrayList<>();

        // 그래프 초기화 -> 일차원으로
        for (int i = 0; i < n * n; ++i) {
            graph.add(new ArrayList<>());
        }

        int curNumber = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                // 현재 방향을 기준으로 네가지 방향을 돌면서 연결 노드 넣어주기
                for (int dir = 0; dir < 4; ++dir) {
                    int nx = i + dx[dir];
                    int ny = j + dy[dir];
                    if (nx < 0 || ny < 0 || nx >= n || ny >= n) {
                        continue;
                    }

                    // 번호 매핑하기
                    int linkNumber = n * nx + ny;
                    graph.get(curNumber).add(new Node(linkNumber, board[nx][ny]));
                }

                ++curNumber;
            }
        }

        return graph;
    }
}