문제

풀이

1. Deque를 이용해 0-1 bfs 진행
2. 다음 갈 곳이 빈 방이면 cnt 그대로 덱 앞에 삽입 벽이면 cnt+1 덱 뒤에 삽입
3. n,m 도달하면 종료

코드

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

public class Main {
    static int n,m;
    static int[][] map;
    static int[][] d=new int[][]{{-1,0},{1,0},{0,-1},{0,1}};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st=new StringTokenizer(br.readLine());
        m=Integer.parseInt(st.nextToken());
        n=Integer.parseInt(st.nextToken());
        map=new int[n][m];
        for(int i=0;i<n;i++){
            String s=br.readLine();
            for(int j=0;j<m;j++){
                int a=s.charAt(j)-'0';
                map[i][j]=a;
            }
        }
        System.out.println(bfs());

    }

    static int bfs(){
        Deque<Step> dq=new LinkedList<>();
        int[][] v=new int[n][m];
        v[0][0]=1;
        dq.addFirst(new Step(0,0,0));
        while(!dq.isEmpty()){
            Step now=dq.pollFirst();
            if(now.y==n-1 && now.x==m-1)return now.cnt;
            for(int i=0;i<4;i++){
                int dy=now.y+d[i][0];
                int dx=now.x+d[i][1];
                if(dy>=n||dx>=m||dy<0||dx<0)continue;
                if(v[dy][dx]==0){
                    if(map[dy][dx]==1){
                        dq.addLast(new Step(dy,dx,now.cnt+1));
                    }
                    else dq.addFirst(new Step(dy,dx,now.cnt));
                    v[dy][dx]=1;
                }
            }
        }
        return 0;
    }

    static class Step{
        int y,x;
        int cnt;

        public Step(int y, int x, int cnt) {
            this.y = y;
            this.x = x;
            this.cnt = cnt;
        }
    }
}

#bfs