알고스팟

📍 문제 설명

 

💡 접근

방문체크하는 배열을 사용하는데 n, m, 벽부순 횟수로 중복 방문 안되도록 하였다.

벽을 적게 부순 횟수부터 계산 하기 위해서 우선순위 큐 사용하였다.

 

-> 어차피 벽인 지점은 방문 할 수 없으므로 2차원 배열 사용해도 된다..

 

👩‍💻 코드

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

public class Main {
    static int n, m, v, e, k, answer, cnt;
    static int[] arr, dis = {-1, 1, 2};
    static long[] dp;
    static int[][] board;
    static boolean[][][] visited;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static ArrayList<Integer> list;
    static StringBuilder sb;
    static Queue<Integer> q;
    public static void main(String[] args) throws IOException {
        Main T = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());

        board = new int[n+1][m+1];

        for(int i = 1; i <= n; i++) {
            String str = br.readLine();
            for(int j = 1; j <= m; j++) {
                board[i][j] = Character.getNumericValue(str.charAt(j-1));
                if(board[i][j] == 1) cnt++;
            }
        }
        visited = new boolean[n+1][m+1][cnt+1];

        T.solution();
     }


    private void solution() {
        PriorityQueue<Point> q = new PriorityQueue<>();
        q.offer(new Point(1, 1, 0));
        visited[1][1][0] = true;

        while(!q.isEmpty()) {
            Point cp = q.poll();
            if(cp.x == n && cp.y == m) {
                System.out.println(cp.crush);
                break;
            }
            for(int i = 0; i < 4; i++) {
                int nx = cp.x + dx[i];
                int ny = cp.y + dy[i];
                if(nx<=0 || ny<=0 || nx>n || ny>m) continue;

                //그냥 갈 수 있는 곳
                if(board[nx][ny] == 0 && !visited[nx][ny][cp.crush]) {
                    //벽 부순적 없는 경로다.
                    visited[nx][ny][cp.crush] = true;
                    q.offer(new Point(nx, ny, cp.crush));
                }
                //벽을 부셔야 갈 수 있는 곳
                else if(board[nx][ny] == 1 && !visited[nx][ny][cp.crush] && cp.crush < cnt) {
                    //벽을 부수면서 가고 있는 경로다.
                    visited[nx][ny][cp.crush] = true;
                    q.offer(new Point(nx, ny, cp.crush+1));
                }
            }
        }

    }

    private static class Point implements Comparable<Point> {
        private int x;
        private int y;
        private int crush;

        public Point(int x, int y, int crush) {
            this.x = x;
            this.y = y;
            this.crush = crush;
        }

        @Override
        public String toString() {
            return "Point{" +
                    "x=" + x +
                    ", y=" + y +
                    ", crush=" + crush +
                    '}';
        }

        @Override
        public int compareTo(Point o) {
            return this.crush - o.crush;
        }
    }
}