[백준] 2206번 벽 부수고 이동하기 (gold 3

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

class Point{
    int x;
    int y;
    int broke;
    int l;
    public Point(int x, int y, int broke, int l){
        this.x=x;
        this.y=y;
        this.broke=broke;
        this.l=l;
    }
}
public class Main {
    static int[] numx={0,0,1,-1};
    static int[] numy={-1,1,0,0};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st=new StringTokenizer(br.readLine());
        int n=Integer.valueOf(st.nextToken());
        int m=Integer.valueOf(st.nextToken());

        int[][] map=new int[n+1][m+1];
        for(int i=1; i<=n; i++){
            String a=br.readLine();
            for(int j=1; j<=m; j++){
                map[i][j]=a.charAt(j-1)-'0';
            }
        }

        Queue<Point> que =new LinkedList<>();
        map[1][1]=-1;
        que.offer(new Point(1,1,0,1));

        int answer=0;
        while(!que.isEmpty()){
            Point temp=que.poll();
            if(temp.x==m && temp.y==n){
                answer=temp.l;
                break;
            }

            for(int i=0; i<4; i++){
                int tx=temp.x+numx[i];
                int ty=temp.y+numy[i];

                if(tx<1 || tx>m || ty<1 || ty>n || map[ty][tx]==2){
                    continue;
                }
                if(map[ty][tx]==1 && temp.broke==0){
                    que.offer(new Point(tx,ty, 1, temp.l+1));
                }
                else if(map[ty][tx]!=0 && temp.broke==1){
                    continue;
                }
                else if(map[ty][tx]==-1 && temp.broke==0){
                    map[ty][tx]=2;
                    que.offer(new Point(tx,ty,temp.broke, temp.l+1));
                }
                else{
                    map[ty][tx]=-1;
                    que.offer(new Point(tx,ty, temp.broke, temp.l+1));
                }
            }
        }

        bw.write(answer==0 ? "-1" : answer+"");
        bw.flush();
    }
}

//생각한 아이디어 일단 벽을 부수면서 가면 그 길은 앵간하면 최소가 될 가능성 존재.
//일단 간 길은 -1로 표시한다. 하지만, 벽을 부순 기회를 사용하여 추후에 막힐 경우도 다분히 존재.
//벽을 부수고 간 애는 0의 가중치 간선으로만 이동가능
//하지만 벽을 한번도 안 부순 친구는 0이나 -1이로도 이동이 가능. 단 벽을 안부수고 이동할때는
//2로 표시 . 왜냐하면 이길은 다시 갈 일이 전혀 없음. 이렇게해서 중복, 왔던 길 재방문안하고,
//최대한 전진으로 나아가면서 파악. n,m에 도달하면 break는 동일.
//최소거리 이므로, 제일 빨리 도달하는애가 거리값이 가장 작은 최솟값이므로.