1249. [S/W - 보급로]

S/W 보급로

문제 : 보급로

설명 :

1. 출발점(0,0)에서 도착점(N-1,N-1)까지 가는 최소 비용을 구하는 문제이다.
2. dist배열을 선언하여 최소값들을 갱신하면서 bfs를 수행한다.
3. 도착점인 dist[N-1][N-1] 이 답이다.

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Solution {
    static int dx[] = { 0, 1, 0, -1};
    static int dy[] = { 1, 0, -1, 0};
    static int[][] map,dist;
    static int N;
    static class Point{
        int x, y, cost;
        Point(int x,int y,int cost){
            this.x = x;
            this.y = y;
            this.cost = cost;
        }
    }
    static Queue<Point> queue = new LinkedList<Point>();
    static void bfs() {
        while(!queue.isEmpty()) {
            Point po = queue.poll();
            for(int i=0;i<4;i++) {
                int x = po.x + dx[i];
                int y = po.y + dy[i];
                 // 범위가 넘어가면 다음으로..
                if(!inRange(x, y)) continue;
                 // 이전 값과 현재 맵의 값을 더하여 다음에 들어갈 수 있는 값을 구한다.
                int nextCost = po.cost + map[x][y];
                 // dist가 max value면 그냥 들어가고 기존에 값이 있더라도 최소값을 넣는다.
                 // 이유는 최소값을 넣는 것으로 이보다 높은 값을 확인할 필요가 없다.
                if(nextCost < dist[x][y]) {
                    dist[x][y] = nextCost;
                    queue.add(new Point(x,y,nextCost));
                }
            }
        }

    }
    static boolean inRange(int x,int y) {
        return 0 <= x && 0 <= y && x < N && y < N;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for(int tc = 1; tc <= T; tc++) {
            N = sc.nextInt();
            map = new int[N][N];
            dist = new int[N][N];
            for(int i=0;i<N;i++) {
                 // dist에 최소값을 갱신하기 위해 최대값을 넣는다.
                Arrays.fill(dist[i], Integer.MAX_VALUE); 
            }
            for(int i=0;i<N;i++) {
                String str = sc.next();
                for(int j=0;j<N;j++) {                    
                    map[i][j] = str.charAt(j) - '0'; 
                }
            }
            queue.add(new Point(0,0,0));
            bfs();    
            System.out.println("#"+tc+" "+dist[N-1][N-1]);
        }
        sc.close();
    }
}