[BOJ 2178] 미로 탐색

문제

• BOJ 2178
• 문제의 저작권은 Baekjoon Online Judge에 있습니다.

접근방식

처음에 아무 의심없이 DFS로 풀었다가 1시간 이상 시간초과로 삽질한 문제이다..
이 문제에서 요구하는 것은 최단 거리이므로 DFS를 사용해서 풀면 모든 경로의 경우의 수를 탐색하므로 시간초과가 발생한다.
그러나 BFS로 풀게되면 입력 조건이 항상 마지막 N,M좌표에 도착하므로 결국 마지막 좌표값이 무조건 최단거리가 된다.

1. 큐에 시작좌표 (1,1)과 칸의 개수 1을 넣는다.
2. 큐가 빌때까지(=마지막 좌표에 올때까지) 다음을 반복한다.
   2-1. 큐에서 하나 꺼내 4방향 탐색으로 다음 좌표를 구한다.
   2-2. 다음 좌표값이 1)범위안이고 2)배열값이 0이 아니고 3)아직 방문하지 않았다면 현재 까지 온 칸수에 1을 더해 배열값을 변경해주고 방문처리 후 큐에 넣어준다.
   [주의] 여기서 방문처리하지 않으면 큐에 있는 다른 좌표에 의해 큐에 중복 삽입될 수 있으므로 메모리 초과가 발생함.
3. while문이 종료되면 탐색이 종료되었으므로 마지막 좌표의 배열값을 출력해주면 그 값이 최단 거리가 된다.

그래도 DFS,BFS는 잘 안다고 생각했는데 반성하게 되는 문제였다 ㅠㅠ

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

//dfs로 푸니 시간초과남 => 최단거리일때는 bfs 사용하기
public class Main {

    static int N, M;
    static int[][] map;
    static boolean[][] visited; //방문 기록
    static int[] di = {-1, 1, 0, 0}; //상하좌우
    static int[] dj = {0, 0, -1, 1};

    static class Point {
        int x;
        int y;

        public Point(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));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][M];
        visited = new boolean[N][M];

        for (int i = 0; i < N; i++) {
            String s = br.readLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = s.charAt(j) - '0';
            }
        }//End input

        Queue<Point> queue = new LinkedList<>();

        queue.add(new Point(0, 0));
        map[0][0] = 1;
        visited[0][0] = true;

        while (!queue.isEmpty()) {
            Point p = queue.poll();

            for (int d = 0; d < 4; d++) {
                int nx = p.x + di[d];
                int ny = p.y + dj[d];

                //현재까지 온 칸 수가 더 많거나 같을때만 큐에 넣기
                if (nx >= 0 && nx < N && ny >= 0 && ny < M && map[nx][ny] != 0 && !visited[nx][ny]) {
                    map[nx][ny] = map[p.x][p.y] + 1; //현재까지 온 칸수 + 1
                    visited[nx][ny] = true; //방문처리
                    queue.add(new Point(nx, ny));
                }
            }//End 4방향 탐색
        }//End BFS

        System.out.println(map[N-1][M-1]);
    }
}