[CLASS 3: BFS] 백준 2178 미로 탐색

2178번: 미로 탐색

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

 

# 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    // 미로 맵
    static int[][] map;
    static int n;  // 세로(행) 길이
    static int m;  // 가로(열) 길이
    static boolean[][] visited; // 방문 여부 체크 배열

    // 상, 하, 좌, 우 방향 이동을 위한 배열
    static int[] dx = { -1, 1, 0, 0 }; // x방향: 위, 아래
    static int[] dy = { 0, 0, -1, 1 }; // y방향: 왼쪽, 오른쪽

    public static void main(String[] args) throws IOException {
        // 빠른 입력을 위한 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        // 첫 줄: n, m 입력받기 (공백 기준)
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        // 미로 정보 저장할 2차원 배열 생성
        map = new int[n][m];

        // 미로의 각 행 입력받기
        for(int i = 0; i < n; i++) {
            String s = br.readLine(); // 한 줄 읽기 (예: "10101")
            for(int j = 0; j < m; j++) {
                map[i][j] = s.charAt(j) - '0'; // 문자 '0' 또는 '1'을 숫자로 변환
            }
        }

        // 방문 여부 배열 초기화
        visited = new boolean[n][m];
        visited[0][0] = true; // 시작 위치 (0,0) 방문 표시

        // BFS 시작
        bfs(0, 0);

        // 최종 목적지까지의 거리 출력
        System.out.println(map[n-1][m-1]);
    }

    // BFS 함수
    public static void bfs(int x, int y) {
        // BFS용 큐 선언, 좌표 (x, y) 형태로 저장
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] {x, y}); // 시작 위치 큐에 추가

        // 큐가 빌 때까지 반복
        while(!q.isEmpty()) {
            int[] now = q.poll();     // 현재 위치 꺼내기
            int nowX = now[0];       // 현재 x좌표
            int nowY = now[1];       // 현재 y좌표

            // 4방향으로 탐색
            for(int i = 0; i < 4; i++) {
                int nextX = nowX + dx[i];
                int nextY = nowY + dy[i];

                // 1. 범위 벗어나면 건너뜀
                if (nextX < 0 || nextY < 0 || nextX >= n || nextY >= m)
                    continue;

                // 2. 이미 방문했거나, 벽(0)이면 건너뜀
                if (visited[nextX][nextY] || map[nextX][nextY] == 0)
                    continue;

                // 3. 이동 가능한 경우
                q.add(new int[] {nextX, nextY}); // 큐에 다음 위치 추가
                map[nextX][nextY] = map[nowX][nowY] + 1; // 거리 누적 저장
                visited[nextX][nextY] = true; // 방문 처리
            }
        }
    }
}