[백준 1261] - 알고스팟

 

문제

• 알고스팟 운영진이 모두 미로에 갇혔다.
  • 미로는 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)으로 이동하려면 벽을 최소 몇 개 부수어야 하는지 구하는 프로그램을 작성하시오.

 

입력

• 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다.
  • 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미한다.
• (1, 1)과 (N, M)은 항상 뚫려있다.

 

출력

• 첫째 줄에 알고스팟 운영진이 (N, M)으로 이동하기 위해 벽을 최소 몇 개 부수어야 하는지 출력한다.

 

 

솔루션

• 우선순위 큐를 이용한 BFS를 수행하였다.
  • 우선순위 큐를 이용한 이유는 현재 지점 값이 적은 부분부터 먼저 탐색 (최단 경로를 구하기 위해) 하기 위함이다. 
  • (1, 1) 부터 (N, M) 지점까지 나아가며 현재 지점의 동서남북 지점을 확인하며 아래와 같은 조건을 확인한다.
    
    • 먼저 방문 여부를 확인한다.
    • 방문하지 않았다면 다음 조건을 한번 더 확인한다.
      • 벽의 유무를 확인한다.
        • 벽이 존재한다면 (값 1) 현재 지점 값 + 1을 하고 우선순위 큐에 삽입한다.
        • 벽이 존재하지 않다면 (값 0) 현재 지점 값을 그대로 가지고 우선순위 큐에 삽입한다.
    • 방문했다면 다른 지점으로 이동하여 위 과정을 다시 수행한다.

 

Code

• 전체 코드 : Solution_1261

(N, M) 위치까지 벽을 부수면서 이동하는 함수

public static int EscapeMaze(int x, int y) {
    PriorityQueue<Point> pq = new PriorityQueue<>();
    int[] dx = { -1, 1, 0, 0 }, dy = { 0, 0, 1, -1 };
 
    visited[x][y] = true;
    pq.offer(new Point(x, y, map[x][y]));
 
    while (!pq.isEmpty()) {
        Point cur = pq.poll();
 
        if (cur.x == N && cur.y == M)
            return cur.value;
 
        for (int i = 0; i < 4; i++) {
            int nx = cur.x + dx[i];
            int ny = cur.y + dy[i];
 
            if (1 <= nx && nx <= N && 1 <= ny && ny <= M) {
                if (!visited[nx][ny]) {
                    visited[nx][ny] = true;
                    if (map[nx][ny] == 0)
                        pq.offer(new Point(nx, ny, cur.value));
                    else
                        pq.offer(new Point(nx, ny, cur.value + 1));
                }
            }
        }
    }
    
    return -1;
}

 

우선순위 큐를 사용하기 위한 클래스

public static class Point implements Comparable<Point> {
    int x, y, value;
 
    public Point(int x, int y, int value) {
        this.x = x;
        this.y = y;
        this.value = value;
    }
 
    @Override
    public int compareTo(Point p) {
        return this.value - p.value;
    }
}

 

결과