[백준] 2178-미로 탐색 (Java)

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

 

문제

 

구현 방식

(0,0) → (m,n) 으로 이동하는데 얼마나 많은 블럭을 이동해야하는지 판단하는 것이 관건인 문제이다. 

 

입력 처리

• 숫자가 공백 없이 주어지므로, 문자열 입력 후 개행(\n)을 기준으로 분리한다.
• 각 줄에서 불필요한 ‘0’을 제거한 뒤 정수 형태로 변환하여 미로를 표현하는 2차원 배열에 저장한다.

 

BFS를 위한 자료구조

• 큐(Queue)를 생성하여 BFS 로직을 구현한다.
• 방문 여부와 이동 거리를 동시에 관리하기 위해 check라는 2차원 배열을 사용한다.
  • check[y][x]에는 '(y, x)까지 이동하는 데 필요한 거리'를 저장한다.
  • 이전 위치의 check 값에 1을 더한 값을 현재 위치에 대입함으로써 거리를 갱신한다.

 

로직

1. 우선 check[0][0]을 방문한 상태(1)로 만들어 준 후, Point 객체를 이용하여 (y, x) 좌표를 입력한 후 큐에 해당 좌표를 삽입한다.
2. 이후 while루프를 큐의 크기가 0이 될 때까지 돌리면서, (y, x) 좌표를 상하좌우로 이동하는 배열을 이용하여 (ny, nx)에 대입하여 이동하도록 한다.
   • 이 때 (y, x)는 현재 좌표를, (ny, nx)는 다음 이동할 좌표를 의미한다.
3. 이 때 오버플로우 및 언더플로우, 갈 수 없는 곳을 방지하는 if문을 만든다.
   만약 해당 조건에 (ny, nx)가 하나라도 걸릴 시, continue 구문을 통해 해당 좌표는 넘어간다.
   또한 check 배열이 0이 아니면(방문한 곳) 마찬가지로 continue 구문을 통해 해당 좌표는 넘어간다.
4. 이후 현재 좌표(y, x)를 큐에서 제거하고, for문이 끝나면(같은 레벨 탐색 종료) 다시 첫 값부터 제거하여 반복하도록 한다.

 

BFS에서 조건문 생성시의 주의사항

오버플로우/언더플로우(배열 범위를 벗어나는 경우)와 이동 불가능한 지역을 구분해야 한다.

if (ny < 0 || ny >= n || nx < 0 || nx >= m || arr[ny][nx] == 0) {
    continue;
}

 

여기서 중요한 점은 '오버플로우/언더플로우 체크'가 먼저 이루어져야 한다는 것이다.

• ny < 0 || ny >= n || nx < 0 || nx >= m : 배열 범위 확인
• arr[ny][nx] == 0 : 이동할 수 없는 지역(벽 등) 판단

만약 방문한 적이 있는 곳(check[ny][nx] != 0)이면, 다시 방문할 필요가 없으므로 continue 구문을 통해 해당 좌표는 넘어간다.

 

정답 코드

import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static Queue<Point> queue = new LinkedList<>();
    static int[][] arr, check;
    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, 1, 0, -1};
    static int ny, nx, n, m;


    static StringBuilder sb = new StringBuilder();

    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());

        arr = new int[n][m];
        check = new int[n][m];

        for (int i = 0; i < n; i++) {
            String s = br.readLine();
            for (int j = 0; j < m; j++) {
                arr[i][j] = s.charAt(j) - '0';
            }
        }

        check[0][0] = 1;
        queue.offer(new Point(0, 0));
        while (!queue.isEmpty()) {
            Point p = queue.poll();
            int y = p.x;
            int x = p.y;
            for (int i = 0; i < 4; i++) {
                ny = y + dy[i];
                nx = x + dx[i];


                if (ny < 0 || ny >= n || nx < 0 || nx >= m || arr[ny][nx] == 0) {
                    continue;
                }
                if (check[ny][nx] != 0) {
                    continue;
                }

                check[ny][nx] = check[y][x] + 1;
                queue.offer(new Point(ny, nx));
            }
        }

        System.out.println(check[n - 1][m - 1]);
    }

}