[2206/BFS] 벽 부수고 이동하기 (JAVA)

문제

---

풀이

나만 어려운 줄 알고 낙담했는데 찾아보니 다같이 어려워하는 문제라 다행이었던 문제다.

처음에는 벽 부수는 것(이하 crash)을 체크하는 변수를 Position 클래스 내 boolean으로 만들어서 한 번만 벽을 부술 수 있도록 코드를 짰다. 또한, visited 배열도 boolean 배열로 사용했다.

하지만 crash가 꼭 일어나야 하는 경로 이전의 최단경로에서 이미 crash가 일어났다면, 그 지점까지의 (최단경로가 아닌) 경로가 존재하더라도 찾아 낼 방법이 없다는 문제가 있었다. 이미 visited로 표시된 정점이라 방문이 되지 않는 것이다. 아래 그림이 반례를 그림으로 표현한 것이다.

따라서 visited 배열에 각 정점의 crash 횟수를 저장하고, Position 객체에 경로의 crash 횟수를 저장하면서 탐색한다.

1. 다음 정점의 crash 횟수보다 여태까지의 경로의 crash 횟수가 더 크면 그 경로는 유효하지 않다.
2. 유효한 경로 + 막히지 않은 다음 정점인 경우, moveCount만 증가시켜 enqueue한다.
3. 유효한 경로 + 벽으로 막힌 다음 정점인 경우, 그 경로에서 crash를 한 번도 하지 않아서 crashCount가 0이면 moveCount와 crashCount 모두 증가시켜 enqueue한다.

---

코드

// 백준 2206 '벽 부수고 이동하기'
// DFS & BFS
// 2020.12.31

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

public class Q2206 {

    private static BufferedReader br;
    private static BufferedWriter bw;

    private static int mapX;
    private static int mapY;
    private static boolean[][] map;
    private static int[][] visited;
    private static int[] X_MOVES = {1, -1, 0, 0};
    private static int[] Y_MOVES = {0, 0, 1, -1};
    private static Position src;
    private static Position dst;

    private static int count = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {

        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        run();
        printAnswer();

        br.close();
        bw.close();
    }

    private static void run() throws IOException {
        initMap();
        initParams();
        bfs();
    }

    private static void initMap() throws IOException {
        getConstants();
        createMap();
        getMap();
    }

    private static void getConstants() throws IOException {
        String line = br.readLine();
        StringTokenizer tk = new StringTokenizer(line);
        mapY = Integer.parseInt(tk.nextToken());
        mapX = Integer.parseInt(tk.nextToken());
    }

    private static void createMap() {
        map = new boolean[mapY + 1][mapX + 1];
    }

    private static void getMap() throws IOException {
        String line;
        for (int i = 1; i <= mapY; i++) {
            line = br.readLine();
            for (int j = 1; j <= mapX; j++) {
                int tmp = Integer.parseInt(String.valueOf(line.charAt(j - 1)));
                if (tmp == 1) map[i][j] = false;
                else map[i][j] = true;
            }
        }
    }

    private static void initParams() {
        initVisited();
        src = new Position(1, 1, 0, 1);
        dst = new Position(mapX, mapY, 0, 0);
    }

    private static void initVisited() {
        visited = new int[mapY + 1][mapX + 1];
        for (int[] row : visited)
            Arrays.fill(row, Integer.MAX_VALUE);
    }

    private static void bfs() {
        Queue<Position> queue = new LinkedList<>();
        queue.offer(src);
        visited[1][1] = 0;

        while (!queue.isEmpty()) {
            Position current = queue.poll();

            if (current.equals(dst)) {
                count = current.moveCount;
                return;
            }

            for (int i = 0; i < X_MOVES.length; i++) {
                int nx = current.x + X_MOVES[i];
                int ny = current.y + Y_MOVES[i];

                if (!isInXBound(nx) || !isInYBound(ny)) continue;

                if (visited[ny][nx] <= current.crashCount) continue;

                if (map[ny][nx]) {
                    visited[ny][nx] = current.crashCount;
                    queue.offer(new Position(nx, ny, current.crashCount, current.moveCount + 1));
                } else {
                    if (current.crashCount == 0) {
                        visited[ny][nx] = current.crashCount + 1;
                        queue.offer(new Position(nx, ny, current.crashCount + 1, current.moveCount + 1));
                    }
                }
            }
        }
    }

    private static boolean isInXBound(int num) {
        return num > 0 && num <= mapX;
    }

    private static boolean isInYBound(int num) {
        return num > 0 && num <= mapY;
    }

    private static void printAnswer() throws IOException {
        checkIfRouteAvailable();
        bw.append(count + "\n");
        bw.close();
    }

    private static void checkIfRouteAvailable() {
        if (visited[mapY][mapX] == Integer.MAX_VALUE)
            count = -1;
    }
}

class Position {

    int x;
    int y;
    int crashCount;
    int moveCount;

    public Position(int x, int y, int crashCount, int moveCount) {
        this.x = x;
        this.y = y;
        this.crashCount = crashCount;
        this.moveCount = moveCount;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Position)) return false;
        Position position = (Position) o;
        return x == position.x && y == position.y;
    }

    @Override
    public int hashCode() {
        return Objects.hash(x, y);
    }
}

---

참고

2206_벽 부수고 이동하기 ( BFS )
[백준 2206] 벽 부수고 이동하기 (Java, BFS)