백준 No.1261 알고스팟 - JAVA

문제

알고스팟 운영진이 모두 미로에 갇혔다. 미로는 N*M 크기이며, 총 1*1 크기의 방으로 이루어져있다. 미로는 빈 방 또는 벽으로 이루어져 있고, 빈 방은 자유롭게 다닐 수 있지만, 벽은 부수지 않으면 이동할 수 없다. 알고스팟 운영진은 여러명이지만, 항상 모두 같은 방에 있어야 한다. 즉, 여러 명이 다른 방에 있을 수는 없다. 

어떤 방에서 이동할 수 있는 방은 사하좌우로 인접한 빈 방이다. 즉, 현재 운영진이 (x,y)에 있을 때, 이동할 수 있는 방은  (x+1, y), (x, y+1), (x-1, y), (x, y-1) 이다. 단, 미로의 밖으로 이동할 수는 업삳.

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

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

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

 

주의할 점

- 문제를 보자마자 다익스트라랑 BFS를 활용한 문제라 생각하여 미로만들기 문제랑 비슷하게 풀었는데 계속 65퍼에서 메모리 초과를 겪으면서 계쏙 틀렸다...... 그래서 결국 미로만들기에서 사용하던 dist 방식을 없애고 Node에 해당 카운트를 넣는 방식으로 변경했다. 그러면서 visited 체크가 필요하여 visited 배열도 추가로 만들었다.

 

풀이-

평소와 다르게 Node에 3가지 값을 넣는다. 세번째 값은 몇개를 부셨는지를 체크할 값이다 원래 같았으면 dist 배열을 만들어 한개씩 체크해 나갔을 텐데 문제에서는 계속 메모리초과를 일으켜서 이런식으로 변경했다.

우선순위 큐를 사용해 깨진 값으로 오름차순 정렬한다.

시작지점은 문제에서는 1,1로 지정했지만 나는 여기서 0,0으로 지정하고 시작했다. 

여기서 node.x와 node.y 가 전체를 탐색했을 경우 해당 값을 solution 변수에 넣는다.

 

아래 for문을 통해 상하좌우를 탐색하고 방문 처리한 곳을 방문하지 않는다. 만약 방문했다면 주어졌던 값이 1인지 아닌지를 체크하여 1일 경우 Node에 brokenValue 값에 1씩 추가해서 넣는다. 맨 처음 시작값은 0이다. 이렇게 할 경우

오른쪽(0,1) 이 map 값이 1일 경우 Node(0,1,1) 이렇게 주어지고 점차 탐색해가면서 broken 값은 증가해 갈 것이다. 

dist 배열을 만든 방식과 거의 동일하다.

 

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

public class Main {

    static int N,M;
    static int map[][];
    static int dx[] = {0,1,0,-1};
    static int dy[] = {1,0,-1,0};
    static String str;
    static int solution = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String [] inputs = br.readLine().split(" ");
        M = Integer.parseInt(inputs[0]);
        N = Integer.parseInt(inputs[1]);

        map = new int[N][M];

        for (int i = 0; i < N; i++) {
            str = br.readLine();
            for(int j=0;j<M;j++){
                   map[i][j] = str.charAt(j)-'0';
            }
        }

        dijs();
        System.out.println(solution);
    }

    private static void dijs() {
        PriorityQueue<Node> queue = new PriorityQueue<>((o1, o2) -> o1.brokenValue - o2.brokenValue);
        queue.add(new Node(0,0,0));
        boolean visited[][] =new boolean[N][M];
        visited[0][0] = true;

        while (!queue.isEmpty()){
            Node node = queue.poll();

            if(node.x == N - 1 && node.y == M-1){
                solution = Math.min(node.brokenValue,solution);
                return;
            }

            for (int i = 0; i < 4; i++) {
                int nextX = node.x + dx[i];
                int nextY = node.y + dy[i];
                int nextBroken = node.brokenValue;

                if(nextX >= 0 && nextY >= 0 && nextX < N && nextY < M){
                       if(!visited[nextX][nextY]){
                           if(map[nextX][nextY] == 1) {
                               queue.add(new Node(nextX,nextY,++nextBroken));
                           } else {
                               queue.add(new Node(nextX,nextY,nextBroken));
                           }
                       }
                        visited[nextX][nextY] = true;
                    }
            }
        }
    }

    static class Node{
        int x;
        int y;

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


}