BOJ02178 미로 탐색

https://www.acmicpc.net/problem/2178 (opens new window)

N x M 크기의 배열로 표현되는 미로가 있다.

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하면 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸수를 구한다. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

BFS

인접한 칸을 탐색하기 위한 BFS 메소드이다. Queue 활용하여 방문하지 않은 칸을 돌며 탐색한다.

private static void bfs(int startX, int startY) {
    Queue<Location> queue = new LinkedList<>();
    queue.add(new Location(startX, startY));

    while (!queue.isEmpty()) {
        Location pollLocation = queue.poll();
        for (int i = 0; i < 4; i++) {
            int x = pollLocation.x + dx[i];
            int y = pollLocation.y + dy[i];
            if (isLocation(x, y)) {
                queue.add(new Location(x, y));
                map[x][y] += map[pollLocation.x][pollLocation.y];
            }
        }
    }
}

아래는 유효한 좌표인지 검증하기 위한 코드이다.

private static boolean isLocation(int x, int y) {
    if (x <= 0 || x > n || y <= 0 || y > m || map[x][y] == 0 || map[x][y] > 1) {
        return false;
    }
    return true;
}

제출 코드

아래는 최종 제출 코드이다.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class BOJ2178 {

    public static int[][] map;
    public static int n;
    public static int m;
    public static int[] dx = {-1, 0, 1, 0};
    public static int[] dy = {0, 1, 0, -1};

    private static class Location {
        private final int x;
        private final int y;

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

    private static void bfs(int startX, int startY) {
        Queue<Location> queue = new LinkedList<>();
        queue.add(new Location(startX, startY));

        while (!queue.isEmpty()) {
            Location pollLocation = queue.poll();
            for (int i = 0; i < 4; i++) {
                int x = pollLocation.x + dx[i];
                int y = pollLocation.y + dy[i];
                if (isLocation(x, y)) {
                    queue.add(new Location(x, y));
                    map[x][y] += map[pollLocation.x][pollLocation.y];
                }
            }
        }
    }

    private static boolean isLocation(int x, int y) {
        if (x <= 0 || x > n || y <= 0 || y > m || map[x][y] == 0 || map[x][y] > 1) {
            return false;
        }
        return true;
    }

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

        n = scanner.nextInt();
        m = scanner.nextInt();
        scanner.nextLine();

        map = new int[n + 1][m + 1];

        for (int i = 1; i <= n; i++) {
            String row = scanner.nextLine();
            for (int j = 1; j <= m; j++) {
                map[i][j] = row.charAt(j - 1) - '0';
            }
        }

        bfs(1, 1);

        System.out.println(map[n][m]);
    }
}

#algorithm #BOJ #그래프 이론 #그래프 탐색 #너비 우선 탐색 #BFS