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

문제 링크

성공 여부(걸린 시간): 성공(15분 30초)

아이디어

우선 출발지와 목적지가 정해져있고 해당 목적지까지 도달하는데에 드는 최소한의 시간을 구하는 것이다.
드는 시간은 이동시간은 없다고 보고 해당 위치의 도로 파손정도 만큼의 시간이 든다고 한다.
그렇게 했을때 든 생각은 BFS이다.

상태는 {x위치, y위치, 해당 위치까지의 가중치합}
만약 다음 위치로 이동할때의 가중치의 합이 이미 방문했던 곳이라고 했을때
전번의 방문보다 가중치가 적다면 계속 진행하고 아니면 continue해준다.

사실 단순 BFS이다.

풀이 코드

import java.io.*;
import java.util.*;
class Solution {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T= Integer.parseInt(br.readLine());
        StringBuilder sb=  new StringBuilder();
        int [] dx = {0, 1, 0, -1};
        int [] dy = {1, 0, -1, 0};
        for(int t=1; t<=T; t++) {
            int N = Integer.parseInt(br.readLine());
            int [][] map = new int [N][N];
            int [][] visited = new int [N][N];
            for(int i=0; i<N; i++) {
                String input = br.readLine();
                for(int j=0; j<N; j++) {
                    map[i][j] = input.charAt(j)-'0';
                    visited[i][j] = Integer.MAX_VALUE;
                }
            }
            ArrayDeque<int[]>q = new ArrayDeque<>();
            q.add(new int[] {0, 0, 0});
            visited[0][0] = 0;
            while(!q.isEmpty()) {
                int [] cur = q.poll();
                int x = cur[0];
                int y = cur[1];
                int cost= cur[2];
                for(int dir =0; dir<4; dir++) {
                    int mx = x+dx[dir];
                    int my = y+dy[dir];
                    if(!canGo(mx, my, N)) {
                        continue;
                    }
                    int mCost = cost+map[mx][my];
                    if(mCost<visited[mx][my]) {
                        q.add(new int[] {mx, my, mCost});
                        visited[mx][my] = mCost;
                    }
                }
            }
            sb.append("#"+t+" "+visited[N-1][N-1]+"\n");
        }
        sb.setLength(sb.length()-1);
        System.out.print(sb);

    }
    static boolean canGo(int x, int y, int N) {
        return x>=0 && y>=0 &&x<N&&y<N;
    }
}