[BOJ/Java] 2178. 미로 탐색

[BOJ/Java] 2178. 미로 탐색

2178번: 미로 탐색

---

문제 해석

이 문제는 주어진 n x m 크기의 미로에서 (1, 1) 위치에서 출발하여 (n, m) 위치까지 이동하는 최소 칸 수를 구하는 문제이다. 각 칸은 이동할 수 있는 칸(1)과 이동할 수 없는 칸(0)으로 구성되어 있다. 이동은 상하좌우 네 방향으로만 가능하다.

풀이 과정

이 문제는 BFS(너비 우선 탐색)를 사용하여 해결할 수 있다. BFS는 시작 노드에서 가까운 노드를 우선적으로 탐색하면서 목표 노드까지의 최단 경로를 찾는 알고리즘이다. 각 위치에 도달했을 때의 이동 횟수를 함께 큐에 저장하여, 목표 위치에 도달할 때의 카운트를 반환하면 그것이 최소 이동 횟수가 된다. 방문한 위치는 다시 방문하지 않도록 방문 상태를 관리한다.

코드

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

public class Main {
    int n, m;
    int[][] graph;
    boolean[][] visited;  // 방문 여부를 저장하는 배열

    public static void main(String[] args) throws IOException {
        new Main().io();
    }

    private void io() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        graph = new int[n][m];
        for (int i = 0; i < n; i++) {
            String s = br.readLine();
            for (int j = 0; j < m; j++) {
                graph[i][j] = s.charAt(j) - '0';  // 미로 정보 입력
            }
        }

        int ans = bfs(0, 0, 1);  // BFS 실행

        bw.write(Integer.toString(ans));
        bw.flush();
        bw.close();
    }

    private int bfs(int x, int y, int cnt) {
        Queue<Point> queue = new ArrayDeque<>();
        queue.offer(new Point(x, y, cnt));  // 초기 위치와 카운트를 큐에 삽입
        visited = new boolean[n][m];
        visited[x][y] = true;

        int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};  // 이동 방향
        while (!queue.isEmpty()) {
            Point p = queue.poll();
            for (int d = 0; d < direction.length; d++) {
                int nx = p.x + direction[d][0];
                int ny = p.y + direction[d][1];

                if(nx == n-1 && ny == m-1) return p.cnt + 1;  // 도착 지점에 도달하면 종료
                
                if(checkStatus(nx, ny)) {
                    visited[nx][ny] = true;  // 방문 표시
                    queue.offer(new Point(nx, ny, p.cnt + 1));
                }
            }
        }
        return -1;
    }

    private boolean checkStatus(int nx, int ny) {
        // 위치 유효성 및 방문 가능 여부 확인
        return 0 <= nx && nx < n && 0 <= ny && ny < m && !visited[nx][ny] && graph[nx][ny] == 1;
    }

    private class Point {
        int x, y, cnt;

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

시간 복잡도 분석

이 문제의 시간 복잡도는 O(N*M)이다. BFS는 각 노드를 한 번씩 방문하고, 각 노드에서는 상하좌우 네 방향을 확인하기 때문에 최악의 경우 모든 노드를 한 번씩 방문할 때의 복잡도를 가진다.

느낀점

미로 탐색과 같은 최단 경로 문제에서 BFS를 활용하면 상대적으로 간단하고 효과적으로 문제를 해결할 수 있다는 점을 다시금 확인할 수 있었다. 각 노드의 방문 여부를 체크하는 것이 중요하며, 이를 통해 불필요한 계산을 줄일 수 있었다.