백준 벽부수고이동하기 2206 java

문제링크

문제 접근

• bfs 돌다가 벽 만나면 그 벽 부수고 그 위치에서 bfs 새로 시작
• 같은 벽 2번 안 부시게

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class baek_2206 {
    static int N,M;
    static int[][] map;
    static boolean[][][] visit;
    static int[] di = {1,-1,0,0};
    static int[] dj = {0,0,1,-1};
    static int answer = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        if(N==1 && M==1){
            System.out.print(1);
            return;
        }
        map = new int[N][M];
        visit = new boolean[N][M][2];

        for(int i=0;i<N;i++){
            String s = br.readLine();
            for(int j=0;j<M;j++){
                map[i][j] = s.charAt(j) - 48;
            }
        }
        bfs();
        System.out.print(answer == Integer.MAX_VALUE ? -1 : answer);
    }

    private static void bfs(){
        Queue<Integer> que = new LinkedList<>();
        que.add(0);
        que.add(0);
        visit[0][0] = true;
        int length = 2;
        while(!que.isEmpty()){
            int size = que.size() / 2;
            for(int s=0;s<size;s++){
                int nowi = que.poll();
                int nowj = que.poll();
                for(int d=0;d<4;d++){
                    int nexti = nowi + di[d];
                    int nextj = nowj + dj[d];
                    System.out.println("ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ");
                    System.out.println("length : "+length+" nexti : "+nexti+" nextj : "+nextj);
                    if(nexti<0 || nexti>=N || nextj<0 || nextj>=M || visit[nexti][nextj]) continue;
                    else if(nexti == N-1 && nextj == M-1){
                        answer = Math.min(answer, length);
                        return;
                    }
                    else if(map[nexti][nextj] == 0){
                        que.add(nexti);
                        que.add(nextj);
                        visit[nexti][nextj] = true;
                    }
                    else if(!visit[nexti][nextj] && map[nexti][nextj] == 1){
                        System.out.println("벽깨고 시작"+" nexti : "+nexti+" nextj : "+nextj+" "+map[nexti][nextj]);
                        break_bfs(nexti, nextj, length);
                    }
                }
            }
            length++;
            if(length >= answer) break;
        }
    }
    private static void break_bfs(int starti, int startj, int length){
        Queue<Integer> que = new LinkedList<>();
        que.add(starti);
        que.add(startj);
        visit[starti][startj] = true;
        boolean[][] visitBreak = new boolean[N][M];
        visitBreak[starti][startj] = true;
        while(!que.isEmpty()){
            int size = que.size() / 2;
            for(int s=0;s<size;s++){
                int nowi = que.poll();
                int nowj = que.poll();
                for(int d=0;d<4;d++){
                    int nexti = nowi + di[d];
                    int nextj = nowj + dj[d];
                    System.out.println("length : "+length+" nexti : "+nexti+" nextj : "+nextj);
                    if(nexti<0 || nexti>=N || nextj<0 || nextj>=M || visitBreak[nexti][nextj] || map[nexti][nextj] == 1 || visit[nexti][nextj]) continue;
                    else if(nexti == N-1 && nextj == M-1){
                        answer = Math.min(answer, length+1);
                        return;
                    }
                    que.add(nexti);
                    que.add(nextj);
                    visitBreak[nexti][nextj] = true;
                }
            }
            length++;
            if(length >= answer) break;
        }
    }
}

결과

• 시간 초과 발생
• 벽 부수고 방문처리, 안부수고 방문처리 구분하긴 했지만 이동했던 점을 계속 bfs 돌아서 시간초과
• 방문한 점은 다시 방문 안하게 객체에 i,j값과 최단거리 값 기록하면서 bfs 돌자

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class baek_2206 {
    static int N,M;
    static int[][] map;
    static boolean[][][] visit;
    static int[] di = {1,-1,0,0};
    static int[] dj = {0,0,1,-1};
    static int answer = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        if(N==1 && M==1){
            System.out.print(1);
            return;
        }
        map = new int[N][M];
        visit = new boolean[N][M][2];

        for(int i=0;i<N;i++){
            String s = br.readLine();
            for(int j=0;j<M;j++){
                map[i][j] = s.charAt(j) - 48;
            }
        }
        bfs();
        System.out.print(answer == Integer.MAX_VALUE ? -1 : answer);
    }
    private static void bfs(){
        Queue<Point> que = new LinkedList<>();
        que.add(new Point(0,0,1,false));
        visit[0][0][0] = true;

        while(!que.isEmpty()){
            Point now = que.poll();
            for(int d=0;d<4;d++){
                int nexti = now.i + di[d];
                int nextj = now.j + dj[d];
                if(nexti<0 || nexti>=N || nextj<0 || nextj>=M) continue;
                else if(nexti == N-1 && nextj == M-1){
                    answer = Math.min(answer, now.cnt+1);
                    continue;
                }
                if(!now.isBreak && map[nexti][nextj] == 1){
                    que.add(new Point(nexti,nextj, now.cnt+1, true));
                }
                else if(map[nexti][nextj] ==0){
                    if(!now.isBreak && !visit[nexti][nextj][0]){
                        que.add(new Point(nexti,nextj, now.cnt+1, false));
                        visit[nexti][nextj][0] = true;
                    }
                    else if(now.isBreak && !visit[nexti][nextj][1]){
                        que.add(new Point(nexti,nextj, now.cnt+1, true));
                        visit[nexti][nextj][1] = true;
                    }
                }
            }
        }
    }
    private static class Point{
        int i;
        int j;
        int cnt;
        boolean isBreak;
        public Point(int i, int j, int cnt, boolean isBreak) {
            this.i = i;
            this.j = j;
            this.cnt = cnt;
            this.isBreak = isBreak;
        }
    }
}

결과

정리

• i,j값만 큐에 넣으면서 하지 말고 객체에 정보를 담아서 bfs 돌자