[SWEA/Java] 1249. 보급로

[SWEA/Java] 1249. 보급로

SW Expert Academy

---

풀이

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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;

public class Solution {
    int n;
    int[][] graph; // 지도 정보를 담을 배열
    int[][] sum; // 출발지부터 해당 위치까지의 최소 복구 시간을 담을 배열
    boolean[][] visited; // 방문 여부를 체크할 배열
    int[][] direction = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } }; // 이동 방향 상하좌우

    public static void main(String[] args) throws IOException {
        new Solution().sol();
    }

    public void sol() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int testCase = Integer.parseInt(br.readLine()); // 테스트 케이스의 수

        for (int t = 1; t <= testCase; t++) {
            n = Integer.parseInt(br.readLine()); // 지도의 크기
            graph = new int[n][n]; // 지도 정보 배열 초기화
            for (int r = 0; r < graph.length; r++) {
                String row = br.readLine();
                for (int c = 0; c < graph.length; c++) {
                    graph[r][c] = row.charAt(c) - '0'; // 지도 정보 입력
                }
            }
            sum = new int[n][n]; // 최소 복구 시간 배열 초기화
            visited = new boolean[n][n]; // 방문 여부 배열 초기화
            
            bfs(); // BFS 수행하여 최소 복구 시간 계산
            
            // 출력
            System.out.println("#" + t + " " + sum[n - 1][n - 1]);
        }
        br.close();
    }

    public void bfs() {
        Deque<Point> deque = new ArrayDeque<>(); // BFS를 위한 덱
        deque.add(new Point(0, 0)); // 출발지 추가
        visited[0][0] = true; // 출발지 방문 표시

        while (!deque.isEmpty()) {
            Point point = deque.poll(); // 덱에서 하나 꺼내기
            int x = point.x; // 현재 위치의 x 좌표
            int y = point.y; // 현재 위치의 y 좌표
            for (int d = 0; d < direction.length; d++) {
                int newX = x + direction[d][0]; // 이동 후 x 좌표
                int newY = y + direction[d][1]; // 이동 후 y 좌표
                if (0 <= newX && newX < n && 0 <= newY && newY < n) { // 이동 가능한 위치인지 확인
                    if (!visited[newX][newY]) { // 아직 방문하지 않은 위치라면
                        visited[newX][newY] = true; // 방문 표시
                        sum[newX][newY] = graph[newX][newY] + sum[x][y]; // 현재 위치까지의 복구 시간 + 이동한 위치의 복구 시간
                        deque.addLast(new Point(newX, newY)); // 덱에 이동한 위치 추가
                    } else { // 이미 방문한 위치라면
                        if (graph[newX][newY] + sum[x][y] < sum[newX][newY]) { // 더 작은 복구 시간이라면
                            sum[newX][newY] = graph[newX][newY] + sum[x][y]; // 복구 시간 업데이트
                            deque.addLast(new Point(newX, newY)); // 덱에 이동한 위치 추가
                        }
                    }
                }
            }
        }
    }

    class Point {
        int x;
        int y;

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