[백준 1261] 알고스팟(Java)

문제 링크 : https://www.acmicpc.net/problem/1261

이 문제는 다익스트라 알고리즘을 이용하여 풀 수 있습니다. 문제를 읽었을 때 벽을 부수는 방식을 카운트하여 BFS 등으로 풀 수도 있겠지만 벽을 부수는 경우 가중치를 1로, 벽을 부수지 않을 경우 가중치를 0으로 하는 그래프로 생각한다면 쉽게 풀 수 있습니다. 최단 거리 배열을 초기화한 후 상하좌우로 이동하면서 최단거리 배열값보다 현재 위치의 벽을 부순 횟수가 더 크면 값을 대체하고 큐에 추가하는 방식으로 풀 수 있습니다.

다음은 코드입니다.

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

class Main{
    static int N,M;
    static int[][] map;
    static int[][] distance;
    static int[] dy = {1,0,-1,0}, dx = {0,1,0,-1};

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        map = new int[N][M];
        for(int i=0;i<N;i++){
            String str = br.readLine();
            for(int j=0;j<M;j++){
                map[i][j] = str.charAt(j)-'0';
            }
        }

        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;
            }
        }

        PriorityQueue<Node> queue = new PriorityQueue<>();
        distance[0][0] = 0;
        queue.add(new Node(0,0,0));
        while(!queue.isEmpty()){
            Node curr = queue.poll();

            for(int i=0;i<4;i++){
                int ny = curr.y + dy[i];
                int nx = curr.x + dx[i];
                int val = curr.val;
                if(ny<0 || ny>=N || nx<0 || nx>=M) continue;

                if(map[ny][nx]==1) val++;
                if(distance[ny][nx] > val){
                    distance[ny][nx] = val;
                    queue.add(new Node(ny,nx,val));
                }
            }
        }

        System.out.println(distance[N-1][M-1]);
    }

    static class Node implements Comparable<Node>{
        int y;
        int x;
        int val;

        Node(int y, int x, int val){
            this.y = y;
            this.x = x;
            this.val = val;
        }

        @Override
        public int compareTo(Node o) {
            return this.val - o.val;
        }
    }
}