[BOJ] 2178. 미로 탐색

https://www.acmicpc.net/problem/2178

접근 방법

미로 탐색이다.

BFS의 전형적인 문제로 내가 방문한 point를 늘려가면서 진행을 하면 문제를 쉽게 풀 수 있다.

Need Know

1. BFS

전체 코드 ( Java )

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Main{
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N, M;
    static int[][] map;
    static int[] aa = {-1,1,0,0};
    static int[] bb = {0,0,1,-1};
    static Point start;
    static Point end;
    static Queue<Point> queue;
    public static void main(String[] args) throws IOException{
        set();
        solve();

        br.close();
        bw.flush();
        bw.close();
    }
    static void set() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N+1][M+1];

        for(int i=0; i<N; i++){
            String str = br.readLine();
            for(int k=0; k<M; k++){
                if(str.charAt(k) == '1'){
                    map[i][k] = 1;
                }
            }
        }
        start = new Point(0,0);
        end = new Point(N,M);
        queue = new LinkedList<>();
        queue.add(start);
    }
    static void solve() throws IOException {
        bfs();

        bw.write(map[N-1][M-1]+"");
    }
    static void bfs(){
        while(!queue.isEmpty()){
            Point now = queue.poll();
            if(now.a == end.a && now.b == end.b){
                break;
            }
            for(int i=0; i<4; i++){
                int na = aa[i] + now.a;
                int nb = bb[i] + now.b;

                if(na < 0 || nb < 0 || na >= N || nb >= M) continue;

                if(map[na][nb] == 1){
                    queue.add(new Point(na,nb));
                    map[na][nb] = map[now.a][now.b] + 1;
                }
            }
        }
    }
    static class Point{
        int a,b;

        public Point(int a, int b) {
            this.a = a;
            this.b = b;
        }
    }
}