[JAVA] 백준 2665 - 미로만들기

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

https://ghcode.tistory.com/288

[JAVA] 1261 - 알고스팟

1261번 알고스팟 문제와 완전히 동일한 문제이다.

알고스팟은 N*M 배열의 최단경로 내의 1의 개수를 세는 문제였다면 이 문제는 N*N에서 0의 개수를 세는 문제이다.

알고스팟 코드를 변형해서 사용했다.

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 temp = par(br.readLine());
        int[] info = {temp,temp};
        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)==1?0:1;
    }
    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;
    }
}