[Java] 백준 2206번 벽 부수고 이동하기 - Bfs

같은 칸에 도달하는 거리를 비교해도

벽을 부수었는지 여부에 따라 따로 비교해야하기 때문에 3중 배열을 사용한다.

어느 칸에 대하여 이미 탐색이 되었다는 것은, 현재의 dis보다 작거나 같은 값이 저장되었으므로 갱신 필요가 없다.

https://velog.io/@yanghl98/%EB%B0%B1%EC%A4%80-2206-%EB%B2%BD-%EB%B6%80%EC%88%98%EA%B3%A0-%EC%9D%B4%EB%8F%99%ED%95%98%EA%B8%B0-JAVA%EC%9E%90%EB%B0%94

[백준] 2206 : 벽 부수고 이동하기 (JAVA/자바)

아이디어에 큰 도움을 받은 글

 

package class4;

import java.util.*;
import java.io.*;

public class g4_2206{
    static boolean[][] map;
    static boolean[][][] check;
    static int n, m, ans = -1;
    static int[] aa = new int[]{-1, 1, 0, 0};
    static int[] bb = new int[]{0, 0, -1, 1};
    // true : 갈수 있는 칸
    public static void main(String[] args){
        FastScanner fs = new FastScanner();
        PrintWriter pw = new PrintWriter(System.out);

        n = fs.nextInt();
        m = fs.nextInt();
        // 0 : 안뚫음 / 1 : 한번 뚫음
        map = new boolean[n + 1][m + 1];
        check = new boolean[n + 1][m + 1][2];
        for (int i=1;i<=n;i++){
            String str = fs.next();
            for (int j=1;j<=m;j++){
                if (str.charAt(j - 1) == '0') map[i][j] = true;
            }
        }

        Queue<Node> q = new LinkedList<>();
        q.add(new Node(1, 1, 1, false));
        bfs(q);
               
        pw.println(ans);
        pw.close();
    }

    static void bfs(Queue<Node> q){
        int size = q.size();
        if (size == 0) return;
        for (int i=0;i<size;i++){
            Node node = q.poll();

            if (node.row == n && node.col == m){
                ans = node.dis;
                return;
            }

            for (int j=0;j<4;j++){
                int nr = node.row + aa[j];
                int nc = node.col + bb[j];

                if (nr == 0 || nc == 0 || nr == n+1 || nc == m+1) continue;

                if (map[nr][nc]){
                    if (!check[nr][nc][0] && !node.broke){
                        q.add(new Node(nr, nc, node.dis + 1, false));
                        check[nr][nc][0] = true;
                    }
                    if (!check[nr][nc][1] && node.broke){
                        q.add(new Node(nr, nc, node.dis + 1, true));
                        check[nr][nc][1] = true;
                    }
                }
                else{
                    if (!check[nr][nc][1] && !node.broke){
                        q.add(new Node(nr, nc, node.dis + 1, true));
                        check[nr][nc][1] = true;
                    }
                }
            }
        }
        bfs(q);
    }

    private static class Node {
        int row, col, dis;
        boolean broke;

        public Node(int row, int col, int dis, boolean broke){
            this.row = row;
            this.col = col;
            this.dis = dis;
            this.broke = broke;
        }
    }


//    ----------input function----------

    static void sort(int[] a){
        ArrayList<Integer> L = new ArrayList<>();
        for (int i : a) L.add(i);
        Collections.sort(L);
        for (int i = 0; i < a.length; i++) a[i] = L.get(i);
    }

    static class FastScanner{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");
        String next(){
            while (!st.hasMoreTokens()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException e){
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt(){
            return Integer.parseInt(next());
        }

        int[] readArray(int n){
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i] = nextInt();
            return a;
        }

        long nextLong(){
            return Long.parseLong(next());
        }
    }
}