[BOJ] 1261 - 알고스팟

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다.

 

문제

www.acmicpc.net/problem/1261

1261번: 알고스팟

난이도: 골드 4

사용언어: JAVA

 

풀이

이 문제는 BFS와 우선순위 큐를 이용해 해결할 수 있습니다. BFS를 이용해 경로를 찾되, 벽을 최소로 부수는 경우를 찾아야 하기 때문에 우선순위 큐를 통해 현 시점에서 가장 적게 벽을 부순 경로부터 체크를 해주면 됩니다.

 

그리고 이미 검사를 한 구역이더라도, 현재의 경로가 벽을 더 적게 부쉈다면, 다시 체크를 해주어야 합니다.

 

import java.io.*;
import java.util.*;
 
class Main {
 
    static int N;
    static boolean[][] arr;
    static boolean[][] visit;
    static int[][] cnt;
 
    static class position implements Comparable<position> {
        int x;
        int y;
        int c;
 
        public position(int x, int y, int c) {
            this.x = x;
            this.y = y;
            this.c = c;
        }
 
        @Override
        public int compareTo(position o) {
            if (this.c > o.c)
                return 1;
            else
                return -1;
        }
    }
 
    static PriorityQueue<position> q = new PriorityQueue<>();
    static int d[][] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
 
    public static void bfs(position p) {
        int nx, ny, nc;
        for (int i = 0; i < 4; i++) {
            nx = p.x + d[i][0];
            ny = p.y + d[i][1];
            nc = p.c;
 
            if (nx >= 0 && nx < N && ny >= 0 && ny < N) { // 격자에서 벗어나는 범위인지 확인
                if (arr[nx][ny] == true) { // 만일 벽이라면 부쉈다고 가정하고 부순 횟수 1 증가
                    nc++;
                }
                if (cnt[nx][ny] > nc || visit[nx][ny] == false) { // 아직 방문하지 않았거나, 더 적게 부수고 온 경로인 경우
                    visit[nx][ny] = true;
                    cnt[nx][ny] = nc; // 최소 부순 횟수 업데이트
                    q.add(new position(nx, ny, nc));
                }
 
            }
        }
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String s;
        N = Integer.parseInt(br.readLine());
        arr = new boolean[N][N];
        visit = new boolean[N][N];
        cnt = new int[N][N];
        for (int i = 0; i < N; i++) {
            s = br.readLine();
            for (int j = 0; j < N; j++) {
                if (s.charAt(j) == '0')
                    arr[i][j] = true;
            }
        }
        q.add(new position(0, 0, 0));
        visit[0][0] = true;
        while (!q.isEmpty()) {
            bfs(q.poll());
        }
 
        bw.write(String.valueOf(cnt[N - 1][N - 1]));
        bw.flush();
        bw.close();
        br.close();
    }
}