boj.kr/2178 미로 탐색 (silver1) 자바 풀이

1. 아래와 같이 bfs방식으로 거리값을 증감하면서 좌표를 탐색하고 목적지에 도착한 경우 최단거리값을 출력

1.1. 출발지 좌표와 초기 거리값을 Queue에 추가

1.2. Queue 가 빌 때까지 아래를 반복

1.2.1. Queue.poll 하여 현재좌표와 거리값을 저장

1.2.2. 현재 좌표가 목적지 좌표이면 거리값을 반환

1.2.3. 상하좌우 좌표를 검사하면서 좌표값이 '1'이고 방문하지 않은 경우 방문체크하고 Queue 에 좌표, 현재거리+1을 add

2. bfs함수 호출 결과를 출력

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static int N;
    static int M;
    static int[][] board;
    static boolean[][] visited;
    static int[] dr = new int[] {0, 0, -1, 1};
    static int[] dc = new int[] {1, -1, 0, 0};

    public static void main(String[] args) {

        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            StringTokenizer sta = new StringTokenizer(br.readLine());
            N = Integer.parseInt(sta.nextToken());
            M = Integer.parseInt(sta.nextToken());
            board = new int[N][M];
            visited = new boolean[N][M];

            for (int r=0; r<N; r++){
                String row = br.readLine();
                for (int c=0; c<M; c++){
                    board[r][c] = Integer.parseInt(String.valueOf(row.charAt(c)));
                }
            }
            System.out.println(bfs());
        } catch (Exception e) {
            e.printStackTrace();
        }

    }

    public static int bfs() {
        Queue<int[]> q = new LinkedList();
        q.add(new int[] {0, 0, 1});

        while (!q.isEmpty()) {
            int now[] = q.poll();
            if (now[0] == N-1 && now[1] == M-1) {
                return now[2];
            }
            for (int i=0; i<4; i++){
                int nr = now[0] + dr[i];
                int nc = now[1] + dc[i];
                if (0<=nr && nr<N && 0<=nc && nc<M) {
                    if (board[nr][nc] == 1 && !visited[nr][nc]){
                        visited[nr][nc] = true;
                        q.add(new int[] {nr, nc, now[2]+1});
                    }
                }
            }
        }

        return 0;
    }

}