[JAVA] 미로탐색 (백준 2178)

유튜버 SecondThread 님이 자주 쓰시는 fastScanner를 연습하고자 bfs 문제중에 가장 기본중의 기본을 풀어보았다.

 

나중에 bfs 로 접근할 일이 있으면 템플릿으로 써도 될듯 하다.

 

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

import static java.lang.System.*;

public class Main {
    private static int n,m;
    private static final int[][] d4  = {{1,0},{0,1},{-1,0},{0,-1}};

    public static void main(String[] args) throws IOException {

        FastScanner fs = new FastScanner();
        n= fs.nextInt();
        m = fs.nextInt();
        int[][] arr = new int[n][m];
        for(int i=0;i<n;i++){
            arr[i] = fs.readArrayFromOneString(m);
        }
//        print2DArray(arr);
        out.println(bfs(arr));



    }

    public static int bfs(int[][] arr){
        int[][] visited = new int[n][m];
        Deque<Loc> q = new ArrayDeque<>();
        q.addLast(new Loc(0,0,1));
        visited[0][0] =1;

        while(!q.isEmpty()){
            Loc cur = q.pollFirst();

            if(cur.x==n-1 && cur.y==m-1){
                return cur.cnt;
            }

            for(int i=0;i<4;i++){
                int nx = cur.x + d4[i][0];
                int ny = cur.y + d4[i][1];

                if(nx>=0 && nx<n && ny>=0 && ny<m && visited[nx][ny]==0 && arr[nx][ny]==1){
                    visited[nx][ny]=1;
                    q.addLast(new Loc(nx,ny,cur.cnt+1));
                }
            }

        }
        return -1; // this is not call
    }




    public static void print2DArray(int[][] a){
        Arrays.stream(a).forEach(
                o->{
                    Arrays.stream(o).forEach(out::print);
                    out.println();
                }
        );
    }

    public static class Loc{
        int x,y,cnt;

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


    public static class FastScanner{

        BufferedReader br = new BufferedReader(new InputStreamReader(in));
        StringTokenizer st = new StringTokenizer("");

        public String next() throws IOException{
            while (!st.hasMoreElements()) st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        int nextInt() throws IOException{
            return Integer.parseInt(next());
        }

        int[] readArray(int n) throws IOException{
            int a[] = new int[n];
            for(int i=0;i<n;i++) a[i]=nextInt();
            return a;
        }
        int[] readArrayFromOneString(int m) throws IOException{
            int a[] = new int[m];
            char[] charr = next().toCharArray();
            for(int i=0;i<m;i++) a[i] = Character.getNumericValue(charr[i]);
            return a;
        }
    }

}