백준 1261번 알고스팟 (자바)

풀이 아이디어

• BFS + Priority Queue
  BFS: visited 배열을 이용해서 방문했던 곳 인지 아닌지 구분하고, 만약 방문했던 곳이라면 이전에 도달했을 때 벽 부순 개수야 현재 벽 부순 개수를 비교해서 더 적을 때만 Priority Queue 에 넣어준다

  Priority Queue: 벽 부순 개수가 적은 순으로 살펴보고 싶으므로 이용

  예를 들어) 벽인 (n,m) 을 살펴보려는데 이전에 벽 부순 개수가 3일 때 도착한 기록이 있고, 현재 벽 부순 개수가 2일 때 -> (n,m) 을 방문하게 되면 현재 벽 부순 개수가 3이 되므로 이전에 살펴본 것과 중복된다! 그러므로 스킵

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

// 알고스팟 (BFS + PriorityQueue)
public class Main {

    static int[][] visited;
    static int[] dr = new int[]{-1, 1, 0, 0};
    static int[] dc = new int[]{0, 0, -1, 1};
    static int n;
    static int m;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        visited = new int[n][m];

        int[][] map = new int[n][m];

        for (int i = 0; i < n; i++) {
            String input = br.readLine();
            for (int j = 0; j < m; j++) {
                map[i][j] = Character.getNumericValue(input.charAt(j));
                visited[i][j] = -1;
            }
        }

        // int[] -> {cnt, r, c} , cnt는 벽 부순 개수
        PriorityQueue<int[]> pq = new PriorityQueue<>((int[] o1, int[] o2) -> {
            return o1[0] - o2[0];
        });
        pq.add(new int[]{0, 0, 0});

        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            if (cur[1] == n - 1 && cur[2] == m - 1) {
                System.out.println(cur[0]);
                break;
            }
            for (int i = 0; i < 4; i++) {
                int nr = cur[1] + dr[i];
                int nc = cur[2] + dc[i];

//                for(int[] v : visited){
//                    System.out.println(Arrays.toString(v));
//                }
//                System.out.println("--------------");
//                맵 범위 밖이면 스킵
                if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
//                방문하지 않은 벽인 경우
                if (visited[nr][nc] == -1 && map[nr][nc] == 1) {
                    visited[nr][nc] = cur[0]+1;
                    pq.add(new int[]{cur[0] + 1, nr, nc});
//                    방문한 곳이지만
                } else if (visited[nr][nc] != -1) {
//                    길인 경우 && 현재 벽 부순 개수가 더 적은 경우 추가
                    if (map[nr][nc] == 0 && visited[nr][nc] > cur[0]){
                        visited[nr][nc] = cur[0];
                        pq.add(new int[]{cur[0], nr, nc});
                    }
//                    벽인 경우 && 현재 벽 부순 개수가 더 적은 경우
                    else if (visited[nr][nc] > cur[0] + 1) {
                        visited[nr][nc] = cur[0] + 1;
                        pq.add(new int[]{cur[0], nr, nc});
                    }
//                    방문하지 않은 길인 경우
                } else if (visited[nr][nc] == -1 && map[nr][nc] == 0) {
                    visited[nr][nc] = cur[0];
                    pq.add(new int[]{cur[0], nr, nc});
                } else {
                    System.out.println("예외 처리 덜 했음");
                }
            }
        }
    }
}