[JAVA] 백준 1261번 - 알고스팟

<문제>

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

N,M미로, 모두 같은 크기의 방, 상하좌우로 움직일 수 있다. 1은 벽, 0은 빈 방인데 빈 방은 자유롭게 다닐 수 있고 벽은 뚫어야 한다.

=> (1,1)에서 (N,M)까지 갈 때 최소로 벽을 몇 개 뚫어야 하는 지 구해야 한다.

<입력>

#1: M N - 가로 세로 (1 ≤ N, M ≤ 100)
#N개: 미로 상태

3 3
011
111
110

<출력>

3

<풀이>

• BFS, DFS에서 했던 2차원 배열 가지고 풀이 하는 게 비슷하다.
• 아래 전체코드에서 적힌 주석으로 이해할 수 있다.

<전체코드>

import java.io.*;
import java.util.*;

class Maze implements Comparable<Maze> {
    int row, col, cost;

    public Maze(int row, int col, int cost) {
        this.row = row;
        this.col = col;
        this.cost = cost;
    }
    @Override
    public int compareTo(Maze maze) {
        return Integer.compare(this.cost, maze.cost);
    }
}

public class Main {
    static int[] dx = {1,0,-1,0};
    static int[] dy = {0,-1,0,1};
    static int[][] maze;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int M = Integer.parseInt(st.nextToken()); //가로
        int N = Integer.parseInt(st.nextToken()); //세로
        maze = new int[N][M];
        for(int i=0; i<N; i++) {
            String row = br.readLine();
            for(int j=0; j<M; j++)
                maze[i][j] = row.charAt(j) - '0';
        }
        int result = dijkstra(N, M);
        System.out.println(result);
    }
    public static int dijkstra(int N, int M) {
        PriorityQueue<Maze> pq = new PriorityQueue<>();
        int[][] distance = new int[N][M];
        for(int i=0; i<N; i++) { //모든 경로 최댓값으로 초기화
            for(int j=0; j<M; j++)
                distance[i][j] = Integer.MAX_VALUE;
        }
        distance[0][0] = 0; // 출발지점을 모두 빈 방으로
        pq.offer(new Maze(0,0,0)); //row, col, cost

        while(!pq.isEmpty()) {
            Maze current = pq.poll();
            if(current.row==N-1 && current.col==M-1) //0번 부터 시작하므로 -1 해야함
                return distance[N-1][M-1];
            for(int i=0; i<4; i++) { //상하좌우 이동
                int nx = current.row + dx[i];
                int ny = current.col + dy[i];
                if(nx>=0 && nx<N && ny>=0 && ny<M) { //2차원 범위내의 있는지
                    int newCost = current.cost + maze[nx][ny];
                    if(newCost < distance[nx][ny]) { //가중치값의 합이 현재 저장된 최단거리값보다 작으면 변경
                        distance[nx][ny] = newCost;
                        pq.offer(new Maze(nx,ny,newCost)); //다음 거 추가
                    }
                }
            }
        }
    	return -1; //불가능 경로
    }
}