[백준] 미로 탐색 (2178번)

문제 이해

• 이 문제는 미로에서 최단 경로를 찾는 문제입니다.
• 시작점(0,0)에서 출발해 도착점(rows-1, cols-1)까지의 최단 거리를 구하는 것이 목표입니다.
• 이동할 수 있는 칸은 '1'로 표시된 칸이며, '0'은 벽이므로 이동할 수 없습니다.

 

핵심 아이디어

1. BFS(너비 우선 탐색):
   • BFS는 모든 경로를 동일한 깊이로 탐색하기 때문에 최단 경로를 찾는 데 유리합니다.
   • 큐(Queue)를 사용해 탐색할 위치를 순서대로 저장하고 처리합니다.
2. 방문 체크:
   • 같은 칸을 중복 방문하지 않기 위해 방문 배열(visit[][])을 사용합니다.
   • 방문한 칸은 다시 탐색하지 않도록 true로 설정합니다.
3. 4방향 탐색:
   • 상하좌우 방향으로 이동하기 위해 델타 배열(dRow, dCol)을 사용합니다.
   • 새로운 좌표가 미로 범위 내에 있고 '1'인 경우에만 이동합니다.
4. 경로가 없을 경우:
   • 도착점에 도달하지 못하면 "경로를 찾을 수 없습니다"를 출력합니다.

 

알고리즘 흐름

1. 입력 받기:
   • 미로의 행과 열 크기, 그리고 미로 데이터를 입력받아 2차원 배열에 저장합니다.
2. BFS 탐색:
   • 큐에 초기 위치 (0,0)과 초기 경로 길이(1)를 넣고 탐색을 시작합니다.
   • 큐에서 꺼낸 위치에서 상하좌우로 이동할 수 있는지 확인합니다.
   • 이동 가능하면 방문 처리 후 큐에 추가합니다.
3. 도착점 도달 여부:
   • 도착점에 도달하면 최단 경로 길이를 출력하고 프로그램을 종료합니다.
   • 탐색이 끝날 때까지 도착점에 도달하지 못하면 "경로를 찾을 수 없습니다"를 출력합니다.

 

---

정답은 여기 클릭

import java.util.*;  // Scanner, Queue 등을 사용하기 위한 라이브러리

public class Main {

    // 미로를 저장할 배열 및 행, 열 크기 정의
    static String[][] maze;
    static int rows, cols;

    // 상하좌우 이동을 위한 방향 배열 (delta 배열)
    static int[] dRow = {1, -1, 0, 0};  // 행 이동 (아래, 위, 그대로)
    static int[] dCol = {0, 0, 1, -1};  // 열 이동 (그대로, 그대로, 오른쪽, 왼쪽)

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);  

        // 미로의 크기 입력 (행과 열)
        rows = in.nextInt();  
        cols = in.nextInt();
        in.nextLine();  // 줄바꿈 처리

        // 미로 배열 초기화
        maze = new String[rows][cols];

        // 미로 정보 입력 (각 줄을 하나씩 읽어서 2차원 배열에 저장)
        for (int i = 0; i < rows; i++) {
            String line = in.nextLine();  // 한 줄씩 입력 받음
            for (int j = 0; j < cols; j++) {
                maze[i][j] = String.valueOf(line.charAt(j));  // 문자열의 각 문자를 저장
            }
        }

        // BFS를 사용해 최단 경로 찾기 시작
        bfs();
    }

    // BFS (너비 우선 탐색) 함수
    public static void bfs() {
        // BFS에 사용할 큐 (좌표와 경로 길이 정보를 저장)
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{0, 0, 1});  // 시작점 (0,0)에서 출발, 초기 경로 길이는 1

        // 방문 여부를 체크하기 위한 배열
        boolean[][] visit = new boolean[rows][cols];
        visit[0][0] = true;  // 시작점 방문 처리

        // 큐가 빌 때까지 탐색 반복
        while (!queue.isEmpty()) {
            int[] current = queue.poll();  // 큐에서 현재 위치 꺼내기
            int curRow = current[0];  // 현재 행
            int curCol = current[1];  // 현재 열
            int steps = current[2];   // 현재까지의 이동 거리

            // 도착점에 도달하면 경로 길이 출력 후 종료
            if (curRow == rows - 1 && curCol == cols - 1) {
                System.out.println(steps);
                return;
            }

            // 상하좌우 4방향으로 이동 시도
            for (int i = 0; i < 4; i++) {
                int newRow = curRow + dRow[i];  // 새로운 행 좌표
                int newCol = curCol + dCol[i];  // 새로운 열 좌표

                // 새로운 좌표가 유효하고(미로 범위 내) '1'이고 방문하지 않은 경우
                if (newRow >= 0 && newCol >= 0 && newRow < rows && newCol < cols
                        && maze[newRow][newCol].equals("1") && !visit[newRow][newCol]) {
                    visit[newRow][newCol] = true;  // 방문 처리
                    queue.add(new int[]{newRow, newCol, steps + 1});  // 큐에 추가 (경로 길이 +1)
                }
            }
        }

        // 도착점에 도달할 수 없는 경우 메시지 출력
        System.out.println("경로를 찾을 수 없습니다");
    }
}