백준 - 2178번 미로탐색(실버 1) (BFS)

미로는 이어져있기 때문에

그림 문제와는 다르게 

while 반복문에 밖에 반복문을 쓸 필요가 없다.

 

그리고 미로문제처럼 최소거리 탐색문제는 보통 배열에 거리를 기록한다.

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

class Main{
    public static int[] dx={0,0,-1,1}; //상하좌우 dx
    public static int[] dy={-1,1,0,0}; //상하좌우 dy
    public static class Pair{
        int x;
        int y;
        public Pair(int x,int y){
            this.x=x;
            this.y=y;
        }
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(
                new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(
                new OutputStreamWriter(System.out));

        String[] str=br.readLine().split(" ");
        int N=Integer.parseInt(str[0]);
        int M=Integer.parseInt(str[1]);
        int[][] miro=new int[N][M];

        for(int i=0;i<N;i++){
            String[] row=br.readLine().split("");
            for(int j=0;j<M;j++){
                miro[i][j]=Integer.parseInt(row[j]);
            }
        }

        Queue <Pair> q=new LinkedList<>();
        boolean[][] visited=new boolean[N][M];

        q.add(new Pair(0,0)); //담기
        visited[0][0]=true; //방문 기록


        while(!q.isEmpty()){
            Pair temp=q.remove();
            int x=temp.x;
            int y=temp.y;

            for(int k=0;k<4;k++){
                int c_x=x+dx[k];
                int c_y=y+dy[k];
                //상하좌우 움직일 좌표

                if(c_x<0||c_x>N-1||c_y<0||c_y>M-1) //경계검사
                    continue;
                if(visited[c_x][c_y]||miro[c_x][c_y]==0)//방문했거나 0이면 다음으로
                    continue;

                q.add(new Pair(c_x,c_y)); //큐에 담기
                visited[c_x][c_y]=true; //방문 기록
                miro[c_x][c_y]=miro[x][y]+1; //거리 기록
            }

        }
        bw.write(Integer.toString(miro[N-1][M-1]));
        bw.flush();
        bw.close();
    }
}