백준 2178: BFS로 미로의 최단 거리 기록하기

백준 2178번: 미로 탐색은 시작 칸에서 도착 칸까지 지나야 하는 최소 칸 수를 구하는 문제입니다. BFS를 사용하고 좌표는 Pos 객체에 담아 큐에 넣었습니다.

다음 칸에 현재 거리 + 1을 기록합니다

상하좌우의 이웃 중 범위 안에 있고, 값이 1이며, 아직 방문하지 않은 칸으로 이동합니다. 큐에 넣으면서 방문 표시를 하고 그 칸의 값을 현재 칸의 값 + 1로 바꿉니다.

시작 칸의 값이 1이므로 거리에는 시작 칸도 들어갑니다. BFS는 가까운 칸부터 탐색하므로 처음 기록한 값이 해당 칸까지의 최소 칸 수가 됩니다. 도착점은 배열의 map[N - 1][M - 1]입니다.

당시 제출 코드

Java

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

class Main {
    static int[][] map;
    static int M, N;
    static Queue<Pos> q = new LinkedList<>();
    static boolean[][] visited;
    static int[] opsX = {-1, 1, 0, 0};
    static int[] opsY = {0, 0, -1, 1};

    // 좌표를 저장하기 위한 클래스
    static class Pos {
        int x;
        int y;

        Pos(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static void main(String[] args) 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());

        // 미로 지도 입력 받기
        map = new int[N][M];
        visited = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            for (int j = 0; j < str.length(); j++) {
                map[i][j] = str.charAt(j)-'0';
            }
        }
        bfs(0, 0);
        bw.write(String.valueOf(map[N - 1][M - 1]));
        bw.flush();
    }

    public static void bfs(int x, int y) throws IOException {
        q.add(new Pos(x, y));
        visited[x][y] = true;

        while (!q.isEmpty()) {
            Pos pos = q.poll();

            for (int i = 0; i < 4; i++) {
                int newX = pos.x + opsX[i];
                int newY = pos.y + opsY[i];

                if (0 <= newX && newX < N && 0 <= newY && newY < M){
                    if (map[newX][newY] == 1 && !visited[newX][newY]) {
                        q.offer(new Pos(newX, newY));
                        visited[newX][newY] = true;
                        map[newX][newY] = map[pos.x][pos.y] + 1;
                    }
                }
            }
        }
    }
}

입력과 거리 기록

미로는 숫자 사이에 공백이 없는 문자열로 들어옵니다. 한 줄을 읽고 charAt()으로 문자를 꺼낸 뒤 '0'을 빼 정수로 바꿨습니다.

탐색 후 배열은 다음과 같습니다. 벽은 0으로 남고 지나갈 수 있는 칸에는 시작점부터의 거리가 적혀 있습니다.

1    0    9    10    11    12    
2    0    8    0    12    0    
3    0    7    0    13    14    
4    5    6    0    14    15

네 방향을 배열로 표현합니다

당시에는 네 방향을 각각 처리했는데 아래처럼 방향을 배열에 담는 방법을 보고 한숨이 나왔습니다. 같은 처리를 반복문 하나로 쓸 수 있다는 것을 뒤늦게 알았습니다.

방향 배열을 사용하는 반복문만 아래에 따로 떼어 놓았습니다. 완성된 메서드는 위 제출 코드에 있습니다.

Java

static int[] opsX = {-1, 1, 0, 0};
static int[] opsY = {0, 0, -1, 1};


for (int i = 0; i < 4; i++) {
    int newX = pos.x + opsX[i];
    int newY = pos.y + opsY[i];

두 배열의 같은 인덱스를 짝지으면 위, 아래, 왼쪽, 오른쪽 이동이 됩니다. 이후 격자 탐색에서도 써먹을 수 있도록 기억해 두려 했습니다.