[SWEA/Java] 1249. 보급로

[SWEA/Java] 1249. 보급로

SW Expert Academy

---

문제 해석

전쟁 피해 지역에서 보급로를 복구하는 작업을 수행해야 한다. 각 지점의 복구 시간이 0부터 9까지의 숫자로 주어지며, 지도는 N x N 격자 형태로 구성되어 있다. 시작점에서 출발하여 종점까지 이동하면서 발생하는 총 복구 시간을 최소화하는 경로를 찾는 것이 목표이다. 이동은 상하좌우로만 가능하다.

풀이 과정

이 문제는 Dijkstra 알고리즘을 적용하여 해결하였다. 이 알고리즘은 시작 정점으로부터 다른 모든 정점까지의 최단 경로를 찾는 데 사용되며, 각 정점의 가중치가 복구 시간에 해당한다.

 

1. 자료 구조: Point 클래스를 정의하여 각 지점의 위치 (x, y)와 해당 지점까지의 누적 복구 시간 w를 관리한다. 우선순위 큐 pq를 사용하여 복구 시간이 짧은 순으로 처리한다.
2. 초기화: 시작점 (0, 0)을 큐에 추가하고 방문 처리한다.
3. BFS 탐색: 큐가 비워질 때까지 반복하여 각 지점에서 가능한 상하좌우 이동을 시도한다. 이동할 수 있는 위치를 큐에 추가하고, 이미 방문한 지점은 건너뛴다. 종점 (N-1, N-1)에 도달하면 그 때의 누적 복구 시간을 결과로 반환한다.

코드

package edu.ssafy.im.SWEA.D4.No1249.SecondTry;

import java.io.*;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

public class Solution {
    private static int N; // 지도의 크기
    private static int[][] map; // 각 지점의 복구 시간을 저장하는 배열
    private final static int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // 이동 가능한 방향

    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 TC = Integer.parseInt(br.readLine()); // 테스트 케이스의 수
        for (int T = 1; T <= TC; T++) {
            N = Integer.parseInt(br.readLine()); // 지도의 크기 입력
            map = new int[N][N];
            for (int i = 0; i < N; i++) {
                char[] row = br.readLine().toCharArray(); // 각 줄의 복구 시간 입력
                for (int j = 0; j < N; j++) {
                    map[i][j] = row[j] - '0'; // 문자를 숫자로 변환하여 저장
                }
            }
            sb.append("#").append(T).append(" ").append(sol()).append("\n"); // 결과 문자열 구성
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private static int sol() {
        Queue<Point> pq = new PriorityQueue<>(); // 우선순위 큐 사용
        pq.offer(new Point(0, 0, 0)); // 시작점 추가
        boolean[][] visited = new boolean[N][N]; // 방문 처리 배열
        visited[0][0] = true;

        while (!pq.isEmpty()) {
            Point p = pq.poll(); // 가장 복구 시간이 짧은 지점을 꺼냄
            for (int[] d : direction) { // 가능한 모든 방향으로 이동 시도
                int nx = p.x + d[0];
                int ny = p.y + d[1];

                if (nx == N-1 && ny == N-1) return p.w; // 종점 도달 시 현재 복구 시간 반환

                if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue; // 지도 범위를 벗어나면 무시
                if (visited[nx][ny]) continue; // 이미 방문했으면 무시

                visited[nx][ny] = true;
                pq.offer(new Point(nx, ny, p.w + map[nx][ny])); // 새 위치를 큐에 추가
            }
        }
        return -1; // 경로를 찾지 못한 경우
    }

    static class Point implements Comparable<Point> {
        int x, y, w; // 위치와 누적 복구 시간

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

        @Override
        public int compareTo(Point o) {
            return this.w - o.w; // 복구 시간 기준으로 비교
        }
    }
}

시간 복잡도 분석

이 알고리즘의 시간 복잡도는 O(V + E log V)이다. 여기서 V는 정점의 수 (N^2), E는 간선의 수 (4N^2), 우선순위 큐를 사용하기 때문에 log V가 추가된다.

느낀점

Dijkstra 알고리즘을 이용하여 주어진 문제의 최적 해를 구하는 과정에서 복잡한 문제도 체계적인 접근을 통해 해결할 수 있음을 확인하였다. 이러한 경험은 앞으로 더 어려운 문제에 직면했을 때 해결 능력을 향상시키는 데 도움이 될 것이다.