[코드트리 챌린지] 5주차 .....

확실히 물오르는 느낌이 들긴한다.

그래프가 예쁘다 뭔가 ,,
다음주에 추락할까봐 두렵기도함

이번주에 푼 문제는 BFS k개의 벽 없애기!
https://www.codetree.ai/missions/2/problems/remove-k-walls?&utm_source=clipboard&utm_medium=text

처음에는 배웠던대로 BFS + 백트래킹(?)으로 풀었는데
원하는대로 답이 안나왔다 ㅜ

import java.util.*;

public class Main {

    public static int N, M, answer, sX, sY, fX, fY, map[][],step[][];
    public static int[] dr = {-1,0,1,0};
    public static int[] dc = {0,1,0,-1};
    public static boolean goal, visited[][], bre[][];
    public static Queue<Node> q = new LinkedList<>();
    public static ArrayList<Node> arr = new ArrayList<>();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        map = new int[N][N];
        
        answer = Integer.MAX_VALUE;
        
        visited = new boolean[N][N];
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                map[i][j] = sc.nextInt();
                //벽이면 벽 배열 넣기
                if(map[i][j]==1){
                    arr.add(new Node(i,j));
                }
            }
        }
        sX = sc.nextInt()-1;
        sY = sc.nextInt()-1;
        fX = sc.nextInt()-1;
        fY = sc.nextInt()-1;
        // 입력끝
        
        ps(0,0);

        answer = (goal)? answer: -1;
        System.out.println(answer);
    }

    public static void ps(int d, int s){
        if(d == M){
            start();
            BFS();
            System.out.println("ds");
            return;
        } else if (s == arr.size()){
            return;
        }
        
        //벽 하나 없애기
        Node now = arr.get(s);
        bre[now.x][now.y] = true;
        ps(d+1,s+1);
        bre[now.x][now.y] = false;
        ps(d,s+1);
    }

    public static void start(){
        visited = new boolean[N][N];
        step = new int[N][N];
        for(int i=0;i<N;i++){
            Arrays.fill(step[i],-1);
        }
        push(sX,sY,0);
    }

    public static void push(int x,int y,int c){
        step[x][y] = c;
        visited[x][y] =true;
        q.add(new Node(x,y));
    }

    public static void BFS(){
        while(!q.isEmpty()){
            Node now = q.poll();
            for(int d=0;d<4;d++){
                int nx = now.x + dr[d];
                int ny = now.y + dc[d];
                if(canGo(nx,ny)){
                    if(nx==fX && ny == fY){
                        goal = true;
                        answer = Math.min(answer,step[now.x][now.y]+1);
                        return;
                    }
                    push(nx,ny,step[now.x][now.y]+1);
                }
            }
        }
    }

    public static boolean isRange(int x,int y){
        return 0 <= x && x < N && 0 <= y && y < N;
    }

    public static boolean canGo(int x,int y){
        if(!isRange(x,y)){return false;}
        if(visited[x][y] || (bre[x][y]==false &&  map[x][y]==1)){return false;}
        return true;
    }

    static class Node{
        int x,y;
        public Node(int x,int y){
            this.x = x;
            this.y = y;
        }
    }
}

BFS를 여러번 돌리면서 큐를 초기화 안한게 문제였다. 뭔가 이런 문제 풀때마다 큐 초기화 안해서 애먹는다 자꾸

이런거 찾을때마다 사이다는 마시는데 자꾸 똑같은거 틀려서 좀 분함

import java.util.*;

public class Main {

    public static int N, M, answer, sX, sY, fX, fY, map[][],step[][];
    public static int[] dr = {-1,0,1,0};
    public static int[] dc = {0,1,0,-1};
    public static boolean goal, visited[][], bre[][];
    public static Queue<Node> q;
    public static ArrayList<Node> arr = new ArrayList<>();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        map = new int[N][N];
        bre = new boolean[N][N];
        answer = Integer.MAX_VALUE;
        
        visited = new boolean[N][N];
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                map[i][j] = sc.nextInt();
                //벽이면 벽 배열 넣기
                if(map[i][j]==1){
                    arr.add(new Node(i,j));
                }
            }
        }
        sX = sc.nextInt()-1;
        sY = sc.nextInt()-1;
        fX = sc.nextInt()-1;
        fY = sc.nextInt()-1;
        // 입력끝
        
        ps(0,0);

        answer = (goal)? answer: -1;
        System.out.println(answer);
    }

    public static void ps(int d, int s){
        if(d == M){
            start();
            BFS();
            return;
        } else if (s == arr.size()){
            return;
        }
        //벽 하나 없애기
        Node now = arr.get(s);
        bre[now.x][now.y] = true;
        ps(d+1,s+1);
        bre[now.x][now.y] = false;
        ps(d,s+1);
    }

    public static void start(){
        visited = new boolean[N][N];
        step = new int[N][N];
        for(int i=0;i<N;i++){
            Arrays.fill(step[i],-1);
        }
        q = new LinkedList<>();
        push(sX,sY,0);
    }

    public static void push(int x,int y,int c){
        step[x][y] = c;
        visited[x][y] =true;
        q.add(new Node(x,y));
    }

    public static void BFS(){
        while(!q.isEmpty()){
            Node now = q.poll();
            for(int d=0;d<4;d++){
                int nx = now.x + dr[d];
                int ny = now.y + dc[d];
                if(canGo(nx,ny)){
                    if(nx==fX && ny == fY){
                        goal = true;
                        answer = Math.min(answer,step[now.x][now.y]+1);
                        return;
                    }
                    push(nx,ny,step[now.x][now.y]+1);
                }
            }
        }
    }

    public static boolean isRange(int x,int y){
        return 0 <= x && x < N && 0 <= y && y < N;
    }

    public static boolean canGo(int x,int y){
        if(!isRange(x,y)){return false;}
        if(visited[x][y] || (bre[x][y]==false &&  map[x][y]==1)){return false;}
        return true;
    }

    static class Node{
        int x,y;
        public Node(int x,int y){
            this.x = x;
            this.y = y;
        }
    }
}