[Java] 백준 2178번: 미로 탐색

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

2178번: 미로 탐색

핵심

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

밑줄 친 부분을 통해서 BFS 풀이법으로 접근해 볼 힌트를 얻을 수 있습니다.

풀이

class Point {
    int y;
    int x;

    Point(int y, int x) {
        this(y, x);
    }
}

문제 풀이에 앞서 좌표를 특정할 Point 클래스를 정의하고 풀어나갑니다.

class BJ2178 {
    private static final Scanner scanner = new Scanner(System.in);

    public static int bfs(boolean[][] map, Point start, Point dest) {
        boolean[][] visited = new boolean[map.length][map[0].length];
        visited[start.y][start.x] = true;

        Deque<Point> deque = new LinkedList<>();
        deque.add(start);

        int count = 0;
        while (!deque.isEmpty()) {
            Point now = deque.poll();
            count++;
            if (now.y == dest.y && now.x == dest.x) {
                break;
            } else {
                if (map[now.y+1][now.x] && !visited[now.y+1][now.x]) {
                    visited[now.y+1][now.x] = true;
                    deque.add(new Point(now.y+1, now.x));
                }
                if (map[now.y][now.x+1] && !visited[now.y][now.x+1]) {
                    visited[now.y][now.x+1] = true;
                    deque.add(new Point(now.y, now.x+1));
                }
                if (map[now.y-1][now.x] && !visited[now.y-1][now.x]) {
                    visited[now.y-1][now.x] = true;
                    deque.add(new Point(now.y-1, now.x));
                }
                if (map[now.y][now.x-1] && !visited[now.y][now.x-1]) {
                    visited[now.y][now.x-1] = true;
                    deque.add(new Point(now.y, now.x-1));
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int[] request = Arrays.stream(scanner.nextLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();
        boolean[][] map = new boolean[request[0]+2][request[1]+2];
        for (int i = 1; i <= request[0]; i++) {
            String[] numbers = scanner.nextLine().split("");
            for (int j = 0; j < numbers.length; j++) {
                map[i][j+1] = numbers[j].equals("1");
            }
        }
        System.out.println(bfs(map, new Point(1, 1), new Point(request[0], request[1])));
    }
}

우선 Main 클래스에서 입력을 받아 문제에서 주어진 미로를 한 번 감싸는 사이즈가 2인 패딩을 줍니다.
그리고 미로와 시작점, 도착점을 지정해서 bfs 메서드를 호출합니다.

BFS 메서드 내에서 방문한 곳을 기록하는 visited 2차 배열을 선언해 줍니다. (사이즈는 map과 같습니다)
시작점을 밟은 상태로 시작하기 때문에 시작점은 미리 true로 설정해줍니다.

deque에 시작점을 넣어주고 Queue에 방문할 수 있는 노드가 있으면 계속 반복하도록 while 문을 시작합니다.
현재 지점을 deque에서 꺼내오고 이동 횟수(count)를 증가시킨 뒤 현재 위치가 목표(dest) 좌표와 같은지 비교합니다.

같지 않다면 아래쪽 -> 오른쪽 -> 위쪽 -> 왼쪽 순으로 현재 노드 기준으로 방문할 수 있는 노드를 체크해서 deque에 넣습니다.
문제의 규칙이 (1, 1)에서 시작해 (N, M)을 탐색하는, 즉 좌상단에서 우하단으로 탐색하기 때문에 위와 같은 순서로 접근해 봅니다.

목표 좌표에 도달했다면 count를 출력해 봅니다. 잘 동작할까요?
틀렸습니다!

풀이(2)

첫 번째 풀이에서는 노드를 이동할 때마다 무조건 count를 합니다.
문제에서 요구한 최소 경로가 아니라 아무 노드로 빠져도 증가하게 되기 때문이죠.

개선을 해봅시다.
우리는 좌표를 특정하는 Point 클래스를 정의했기 때문에 이 클래스를 활용해볼 수 있겠네요.

Point 클래스 필드에 현재 좌표가 몇 개의 길을 거쳐왔는지 즉 depth를 갖도록 해보면 어떨까요?

class Point {
    int y;
    int x;
    int depth;

    Point(int y, int x) {
        this(y, x, 1);
    }

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

class BJ2178 {
	// ...
    
    public static int bfs(boolean[][] map, Point start, Point dest) {
    	// ...
        
        while (!deque.isEmpty()) {
            Point now = deque.poll();
            if (now.y == dest.y && now.x == dest.x) {
                count = now.depth;
                break;
            } else {
                if (map[now.y+1][now.x] && !visited[now.y+1][now.x]) {
                    visited[now.y+1][now.x] = true;
                    deque.add(new Point(now.y+1, now.x, now.depth+1));
                }
                if (map[now.y][now.x+1] && !visited[now.y][now.x+1]) {
                    visited[now.y][now.x+1] = true;
                    deque.add(new Point(now.y, now.x+1, now.depth+1));
                }
                if (map[now.y-1][now.x] && !visited[now.y-1][now.x]) {
                    visited[now.y-1][now.x] = true;
                    deque.add(new Point(now.y-1, now.x, now.depth+1));
                }
                if (map[now.y][now.x-1] && !visited[now.y][now.x-1]) {
                    visited[now.y][now.x-1] = true;
                    deque.add(new Point(now.y, now.x-1, now.depth+1));
                }
            }
        }
        return count;
	}
}

현재 좌표에서 갈 수 있는 다른 노드를 추가할 때 현재 좌표가 거쳐온 depth+1을 넣어주면 목표 지점에 도달했을 때의 depth가 문제에서 요구한 가장 빠르게 (적게) 접근한 최소 칸의 수 일 것입니다.