📖 [백준알고리즘 풀이] Q.1261 알고스팟 문제 풀이 - java

📖 문제

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

알고스팟 운영진이 모두 미로에 갇혔다. 미로는 NM 크기이며, 총 11크기의 방으로 이루어져 있다. 미로는 빈 방 또는 벽으로 이루어져 있고, 빈 방은 자유롭게 다닐 수 있지만, 벽은 부수지 않으면 이동할 수 없다.

알고스팟 운영진은 여러명이지만, 항상 모두 같은 방에 있어야 한다. 즉, 여러 명이 다른 방에 있을 수는 없다. 어떤 방에서 이동할 수 있는 방은 상하좌우로 인접한 빈 방이다. 즉, 현재 운영진이 (x, y)에 있을 때, 이동할 수 있는 방은 (x+1, y), (x, y+1), (x-1, y), (x, y-1) 이다. 단, 미로의 밖으로 이동 할 수는 없다.

벽은 평소에는 이동할 수 없지만, 알고스팟의 무기 AOJ를 이용해 벽을 부수어 버릴 수 있다. 벽을 부수면, 빈 방과 동일한 방으로 변한다.

만약 이 문제가 알고스팟에 있다면, 운영진들은 궁극의 무기 sudo를 이용해 벽을 한 번에 다 없애버릴 수 있지만, 안타깝게도 이 문제는 Baekjoon Online Judge에 수록되어 있기 때문에, sudo를 사용할 수 없다.

현재 (1, 1)에 있는 알고스팟 운영진이 (N, M)으로 이동하려면 벽을 최소 몇 개 부수어야 하는지 구하는 프로그램을 작성하시오.

🔍 접근법

BOJ Q.1261 알고스팟 문제입니다. N*M 크기의 미로가 주어지고 미로는 빈 방 또는 벽으로 이루어져 있습니다.

빈 방은 그냥 지나다닐 수 있고 벽은 부수고 이동이 가능합니다.

이동은 인접한 동서남북으로만 가능합니다.

1,1 지점에서 출발한다고 할 때 N,M까지 이동을 하려고 하는데 이때 벽을 최소 몇 개를 부숴야하는지를 구하는 문제입니다.

문제를 보면 N*M 크기의 미로가 주어지고 동서남북으로 이동이 가능하니

일반적인 bfs 탐색으로 풀이가 가능해보입니다.

하지만, 이 문제에서 핵심인 가중치가 이동거리라면 일반적인 bfs 탐색으로 풀이가 가능했겠지만

여기서 가중치는 이동거리가 아닌 벽을 부수는 갯수입니다.

벽이 있냐 없냐에 따라 부수고 이동할 수도 있고 (1) 그냥 이동할 수도 있습니다. (0)

가중치가 1이 아닌 1 또는 0인 그래프를 탐색해야 하므로

다익스트라 알고리즘을 이용해 풀이가 가능합니다.

보통의 최단 경로를 구할 때 처럼 다익스트라를 위한 테이블을 만듭니다.

그리고 대신, 거리를 중심으로 보는 것이 아니라 벽을 부수는 것을 중심으로

현재 위치에서 각 다음 위치(동서남북)로 이동할 때마다 더 최소한으로 벽을 부수고 이동할 수 있다면 갱신해주면 됩니다.

if(distance[x][y] > distance[currentNode.x][currentNode.y]+maze[x][y] ){
                    distance[x][y] = distance[currentNode.x][currentNode.y]+maze[x][y];
                    priorityQueue.add(new Node(x,y,distance[x][y]));
}

💻 코드

package problem.shortest.Q1261;

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

public class Main_1261 {

    static int moveX[] = {0,0,-1,1};
    static int moveY[] = {-1,1,0,0};
    static int maze[][];
    static int distance[][];
    static int n,m;

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

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

        @Override
        public int compareTo(Node target) {
            // 작은 거리 비용이 먼저 오도록
            return this.distance - target.distance;
        }
    }

    public static void main(String[] args) throws IOException {
        input();
        solve();
        System.out.println(distance[n-1][m-1]);
    }

    private static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String temp[] = br.readLine().split( " ");
        m= Integer.parseInt(temp[0]);
        n= Integer.parseInt(temp[1]);
        maze = new int[n][m];
        distance = new int[n][m];
        for(int i=0; i<n; i++){
            Arrays.fill(distance[i],Integer.MAX_VALUE);
        }

        for(int i=0; i<n; i++){
            temp = br.readLine().split("");
            for(int j=0; j<m; j++){
                maze[i][j] = Integer.parseInt(temp[j]);
            }
        }
        br.close();
    }
    private static void solve(){
        PriorityQueue<Node> priorityQueue = new PriorityQueue<>();
        priorityQueue.add(new Node(0,0,0));
        distance[0][0] = 0;

        while (! priorityQueue.isEmpty()){
            Node currentNode = priorityQueue.poll();
            if(currentNode.x == n-1 && currentNode.y == m-1){
                return;
            }

            for(int i=0; i<4; i++){
                int x = currentNode.x +moveX[i];
                int y = currentNode.y + moveY[i];
                if(x < 0 || y <0 || x >= n || y >= m){
                    continue;
                }
                if(distance[x][y] > distance[currentNode.x][currentNode.y]+maze[x][y] ){
                    distance[x][y] = distance[currentNode.x][currentNode.y]+maze[x][y];
                    priorityQueue.add(new Node(x,y,distance[x][y]));
                }
            }
        }
    }
}

Written on April 21, 2021