[JAVA][Baekjoon] 2178번 미로 탐색 🌟🌟

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

 

📌 접근 방식

1️⃣ 문제 분석

• 미로는 2D 배열로 표현되고, 1은 이동 가능한 칸, 0은 이동 불가한 칸으로 나눔
• 출발점 (1, 1)에서 도착점 (N, M)까지 이동하며 최소 칸 수를 구해야 함
• BFS를 사용해 너비 우선 탐색으로 최단 거리를 구하면 된다!

2️⃣ 핵심 아이디어

• BFS의 특징: 가까운 칸부터 탐색하기 때문에 최단 거리 계산에 적합함
• 큐를 사용해 (x, y) 좌표를 관리하고, 방문 여부는 visited 배열로 체크!
• 미로 배열 A 자체를 거리 계산 용도로 활용해, 도착지의 값을 바로 출력하도록 설계

3️⃣ 이동 방향 설정

• 상, 하, 좌, 우로 이동하므로, 이를 dx, dy 배열로 관리
• dx = {0, 1, 0, -1}, dy = {1, 0, -1, 0}로 간결하게 처리!

[알고리즘] 너비 우선 탐색 : BFS(Breadth-First-Search)

 

✅ PASS CODE

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

public class Main {
    static int N;
    static int M;
    static boolean[][] visited;
    static int [][]A;
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};
    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());
        A = new int[N][M];
        visited = new boolean[N][M];
        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            String line = st.nextToken();
            for(int j=0; j<M; j++) {
                A[i][j] = Integer.parseInt(line.substring(j, j+1));
            }
        }
        BFS(0, 0);
        System.out.println(A[N-1][M-1]);

    }
    private static void BFS(int i, int j) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[] {i, j});
        visited[i][j] = true;
        while(!queue.isEmpty()) {
            int cur[] = queue.poll();;
            for(int k=0; k<4; k++) {
                int x = cur[0] + dx[k];
                int y = cur[1] + dy[k];
                if(x >= 0 && y >= 0 && x < N && y < M ) {
                    if(!visited[x][y] && A[x][y] != 0) {
                        visited[x][y] = true;
                        A[x][y] = A[cur[0]][cur[1]]+1;
                        queue.add(new int[] {x, y});
                    }
                }
            }

        }
    }
}

 

🧐 느낀점

이 문제를 풀면서 BFS가 최단 거리 문제에 정말 적합하다는 걸 다시 한번 느꼈다 🙌
특히, 미로 배열 A를 그대로 활용해 거리 정보를 업데이트하는 방법이 효율적이었다.

처음에는 BFS를 이용하면 유용할 것이라고 생각은 들었으나, 이중 배열을 이용해 어떻게 구현해야할지도 막막했다..😅 또, 상하좌우로 이동하는 로직을 어떻게 짜야 할지도 어려웠다… 😅 그래도 고민해보며 차근차근 고민하면서 풀어보니 결국 해낼 수 있었다!

다음엔 DFS와 비교해 좀 더 복잡한 미로 탐색도 도전해보고 싶다 🚀🚀