1249. [S/W 문제해결 응용] 4일차 - 보급로 - 자바(JAVA)

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

SW Expert Academy

 

문제 해석

도로를 지나가야 하는데 도로가 파여진 깊이에 비례하여 복구 시간이 증가합니다.

출발지에서 도착지까지 가는 경로 중에서 복구 시간이 가장 짧은 경로에 대한 총 복구 시작을 구하시오.

깊이가 1이라면 복구에 드는 시간은 1입니다.

각 테스트 케이스마다 지도의 크기(N x N)이 주어지며 출발지(S)와 도착지(G)는 좌상단과 우하단이 됩니다.

 

문제 풀이 전 설계

(0,0) -> (N-1, N-1) 으로 이동하는 경로의 합이 가장 작은 곳을 구해야 합니다.

 

접근1 DP

어떤칸을 기준으로 상하좌우로 접근이 가능한데 상하좌우의 값이 항상 최적의 해가 아니기 때문에 불가능할것 같습니다.

 

접근2 DFS 백트레킹

탐색을 쭉하면서 N-1,N-1에 도착한다면 지나온 경로의 총 비용으로 경로를 모두 업데이트합니다.

이후에 가는길의 비용이 방문된 경로의 총비용보다 높으면 지나가지 못합니다.

 

접근3

그래프의 최단경로를 찾는 문제와 동일하기 때문에 다익스트라로 접근해보겠습니다.

 

아래코드는 다익스트라로 구현된 코드입니다.

코드

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

public class Solution_1249_보급로 {

    static class Pos{
        int y;
        int x;
        int sum;

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

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

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

        StringBuilder sb = new StringBuilder();
        String tempString = null;
        int result;
        for(int tc=1; tc<=T; tc++){
            result = Integer.MAX_VALUE;
            int n = Integer.parseInt(br.readLine());
            int[][] board = new int[n][n];
            for(int y=0; y<n; y++){
                tempString = br.readLine();
                for(int x=0; x<n; x++){
                    board[y][x] = Character.getNumericValue(tempString.charAt(x));
                }
            }
            //입력 끝
            PriorityQueue<Pos> bfsQ = new PriorityQueue<>((c1,c2) -> c1.sum - c2.sum);
            boolean[][] visited = new boolean[n][n];

            bfsQ.add(new Pos(0,0,board[0][0]));
            visited[0][0] = true;

            while (!bfsQ.isEmpty()){
                Pos curPos = bfsQ.poll();
                int curY = curPos.y;
                int curX = curPos.x;
                int curSum = curPos.sum;
                if(curX == n-1 && curY == n-1){
                    result = curSum;
                    break;
                }

                for(int d = 0; d<4; d++){
                    int tempY = curY + dy[d];
                    int tempX = curX + dx[d];
                    if(tempY < 0 || tempX < 0 || tempY >= n || tempX >=n  || visited[tempY][tempX]){
                        continue;
                    }
                    visited[tempY][tempX] = true;
                    bfsQ.add(new Pos(tempY,tempX, curSum + board[tempY][tempX]));
                }
            }

            sb.append("#" + tc + " " + result + "\n");
        }

        System.out.print(sb.toString());
    }
}