[JAVA] 1261 - 알고스팟

https://www.acmicpc.net/problem/1261

0과 1로 이루어진(0->빈 방, 1 -> 벽)N*M의 배열이 주어졌을 때, 0,0에서 (N-1,M-1)까지 이동할 때 부숴야하는 벽의 최소 갯수를 구하는 문제이다.

빈방으로만 목적지까지 이동할 수 있으면 답은 반드시 0이고, 길이 막혀있는 경우에만 벽을 부수는데 부순 벽의 개수가 최소이게끔 하는 문제이다. 따라서 0과 1을 각각 가중치로 생각하고 다익스트라를 이용해 해결했다.

 

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

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] info = getArray(br.readLine());
        char[][] map = new char[info[1]][info[0]];
        int[][] dist = new int[info[1]][info[0]];
        for (int i = 0; i < map.length; i++) {
            map[i] = br.readLine().toCharArray();
            Arrays.fill(dist[i],Integer.MAX_VALUE);
        }
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        boolean[][] visited = new boolean[info[1]][info[0]];
        dist[0][0] = 0;
        pq.offer(new Edge(0,0));
        while(!pq.isEmpty()){
            Edge e = pq.poll();
            int i = e.i;
            int j = e.j;
            int weight = dist[i][j];
            if(visited[i][j]) continue;
            visited[i][j] = true;
            if(i==info[1]-1&&j==info[0]-1){
                System.out.println(weight);
                return;
            }
            for (int k = 0; k < 4; k++) {
                if(check(i+dx[k], j+dy[k],map,visited)){
                    int cost = getCost(map[i+dx[k]][j+dy[k]]);
                    if(dist[i+dx[k]][j+dy[k]] > weight + cost){
                        dist[i+dx[k]][j+dy[k]] =  weight + cost;
                        Edge target = new Edge(i+dx[k], j+dy[k]);
                        target.weight = dist[i+dx[k]][j+dy[k]];
                        pq.offer(target);
                    }
                }
            }
        }
    }
    static boolean check(int i, int j, char[][] map, boolean[][] visited){
        if(i<0||i>=map.length) return false;
        if(j<0||j>=map[0].length) return false;
        if(visited[i][j]) return false;
        return true;
    }

    static int getCost(char c){
        return Character.getNumericValue(c);
    }
    static int par(String s) {
        return Integer.parseInt(s);
    }

    static int[] getArray(String s) {
        return Arrays.stream(s.split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}

class Edge implements Comparable<Edge>{
    int i;
    int j;
    int weight = 0;
    Edge(int i, int j){
        this.i = i;
        this.j = j;
    }
    @Override
    public int compareTo(Edge o) {
        return this.weight - o.weight;
    }
}