[BOJ] 백준 1261번 : 알고스팟 (JAVA)

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

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)까지 최단거리로 가라고 요구한 것이 아니라, 벽을 최소한으로 부수고 가라고 요구했기때문이죠. 그래서 우리는 벽을 부순 개수에 대해서 오름차순 정렬하면서 poll을 하면 됩니다.

이 외에는 흔히 사용하는 BFS 코드를 작성하시면 됩니다.

아래는 위 내용을 정리한 소스코드입니다.

 

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
class Point implements Comparable<Point> {
    int x;
    int y;
    int cnt; // 벽을 부순 개수
 
    Point(int x, int y, int cnt) {
        this.x = x;
        this.y = y;
        this.cnt = cnt;
    }
 
    @Override
    public int compareTo(Point o) {
        return cnt - o.cnt;
    }
}
 
public class Main {
    static int[] rangeX = { -1, 0, 1, 0 };
    static int[] rangeY = { 0, 1, 0, -1 };
    static int N, M;
    static int[][] map;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        M = Integer.parseInt(st.nextToken()); // 가로
        N = Integer.parseInt(st.nextToken()); // 세로
 
        map = new int[N + 1][M + 1];
 
        for (int i = 1; i <= N; i++) {
            String input = br.readLine();
            for (int j = 1; j <= M; j++) {
                map[i][j] = Character.getNumericValue(input.charAt(j - 1));
            }
        }
 
        int ans = BFS(1, 1);
 
        bw.write(ans + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
 
    public static int BFS(int x, int y) {
        // 벽을 부순 개수를 오름차순으로 정렬하도록 설정.
        PriorityQueue<Point> q = new PriorityQueue<>();
 
        q.offer(new Point(x, y, 0));
        boolean[][] visit = new boolean[N + 1][M + 1];
        visit[x][y] = true;
 
        int dx, dy;
        while (!q.isEmpty()) {
            Point p = q.poll();
 
            // 도착점에 도달했으면 종료.
            if (p.x == N && p.y == M) {
                return p.cnt;
            }
 
            for (int i = 0; i < 4; i++) {
                dx = p.x + rangeX[i];
                dy = p.y + rangeY[i];
 
                if (dx < 1 || dy < 1 || dx > N || dy > M) {
                    continue;
                }
 
                if (!visit[dx][dy] && map[dx][dy] == 0) {
                    visit[dx][dy] = true;
                    q.offer(new Point(dx, dy, p.cnt));
                }
 
                if (!visit[dx][dy] && map[dx][dy] == 1) {
                    visit[dx][dy] = true;
                    q.offer(new Point(dx, dy, p.cnt + 1));
                }
            }
        }
        return 0;
    }
 
}

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.