[백준] 2178. 미로탐색 - JAVA

1. 문제

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

 

2. 풀이 과정

(1, 1)에서 시작해서 (N, M)에 도달하기 위한 최단거리를 구하는 문제이다.

각 영역은 0 또는 1인데, 0으로 이동할 수 없다.

 

처음에는 이 문제를 DFS로 접근했었다. 하지만 시간초과가 발생하는 것이었다.

 

DFS 접근 방법의 문제

DFS는 모든 경로를 끝까지 탐색하면서, MIN 값을 갱신해야 한다.

최단경로를 보장하지 않으므로 모든 경우의 수를 전부 확인해야 한다.

그래서 시간초과가 발생하는 것이었다.

 

문제 접근

이 문제는 BFS로 접근해야 효율적으로 풀 수 있다.

BFS는 같은 깊이의 노드부터 순차적으로 탐색한다. 이동거리를 누적하면 결국 N, M에 도달하는 시점이 최단거리가 된다.

 

1. 큐에 시작점 (0, 0)을 넣는다.

• 문제에서는 시작점: (1, 1), 종료지점: (N, M)이라고 하지만, 배열의 인덱스가 0라는 것을 감안해서 시작점: (0, 0), 종료지점: (N - 1, M - 1)로 가정한다.

int x, y = 0
Queue<Point> q = new LinkedList<>();
q.offer(new Point(x, y));

 

2. 이동할 수 있는 방향은 북, 서, 남, 동이다. 방향 백터로 4가지 방향에 대해서 탐색한다.

• 이동할 칸이 범위를 벗어나는지 검사하고 벗어나는 경우 PASS
• 이동할 칸이 1이 아니라면 PASS => (이동할 수 없는 영역이거나 이미 방문한 영역)
• 이동 가능한 칸이라면, 현재 칸의 값에서 +1을 새로운 칸에 기록한다 => 누적 거리 저장

while (!q.isEmpty()) {
    Point cur = q.poll();
    for (int i = 0; i < 4; i++) { // 4가지 방향 탐색
        // 다음 방문 영역
        int nx = cur.x + dx[i];
        int ny = cur.y + dy[i];
        
        // 범위를 벗어나거나, 이미 방문했거나 이동할 수 없는 칸
        if (nx < 0 || nx >= N || ny < 0 || ny >= M || map[nx][ny] != 1) {
            continue;
        }
        map[nx][ny] = map[cur.x][cur.y] + 1; // 누적거리 저장
        q.offer(new Point(nx, ny)); // 큐에 추가
    }
}

 

3. BFS를 통해 (N - 1, M - 1) 칸의 값이 곧 최단거리가 된다.

 bw.write(map[N - 1][M - 1] + "\n");

 

 

3. 코드

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static int N;
    static int M;
    static int[][] map;
    static int[] dx = {0, -1, 0, 1};
    static int[] dy = {-1, 0, 1, 0};

    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][M];

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

        bfs(0, 0);

        bw.write(map[N - 1][M - 1] + "\n");
        bw.flush();
        bw.close();
    }

    static void bfs(int x, int y) {
        Queue<Point> q = new LinkedList<>();
        q.offer(new Point(x, y));

        while (!q.isEmpty()) {
            Point cur = q.poll();
            for (int i = 0; i < 4; i++) {
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];
                if (nx < 0 || nx >= N || ny < 0 || ny >= M || map[nx][ny] != 1) {
                    continue;
                }
                map[nx][ny] = map[cur.x][cur.y] + 1;
                q.offer(new Point(nx, ny));
            }
        }
    }

    static class Point {
        int x;
        int y;

        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}