[BOJ/GoldIII] 2206. 벽 부수고 이동하기

2206번: 벽 부수고 이동하기

• 725ms
• bfs

dfs로는 시간초과가 나고 단순 bfs 로 해결할 수 없는 문제이다.

 

디버깅을 통해 벽을 부수고 이동했을 경우 방문체크와 벽을 부수지 않고 이동했을 경우의 방문체크를 다르게 해줘야 정답이 나온다는 것을 깨달았고 방문체크 배열을 3차원 배열로 선언하여 체크했다.

 

다음과 같이 벽을 부순 경우와 부수지 않은 경우를 나눠 방문체크 해준다. 벽을 부수지 않고 이동한 경로는 visited[][][0] 벽을 부수고 이동한 경로는 visited[][][1] 로 체크한다.

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

public class Main {

    static int n, m, result = Integer.MAX_VALUE;
    static int[][] board;
    static boolean[][][] visited;
    static boolean flag;
    static int[] dx = { 1, -1, 0, 0 };
    static int[] dy = { 0, 0, 1, -1 };

    static class Node {
        int x;
        int y;
        int count;
        boolean flag;

        public Node(int x, int y, int count, boolean flag) {
            this.x = x;
            this.y = y;
            this.count = count;
            this.flag = flag;
        }
    }

    public static void bfs() {
        Queue<Node> q = new LinkedList<Main.Node>();
        q.offer(new Node(1, 1, 1, false));
        visited[1][1][0] = true;

        while (!q.isEmpty()) {
            Node now = q.poll();

            if (now.count > result)
                continue;
            if (now.x == n && now.y == m)
                result = Math.min(result, now.count);

            for (int i = 0; i < 4; i++) {
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];

                if (nx > 0 && nx <= n && ny > 0 && ny <= m) {

                    // 벽이 아닐 경우
                    if (board[nx][ny] == 0) {
                        // 벽을 한 번 부쉈고, 이동하지 않은 경로라면
                        if (now.flag && !visited[nx][ny][1]) {
                            q.offer(new Node(nx, ny, now.count + 1, now.flag));
                            visited[nx][ny][1] = true;
                        } 
                        // 벽을 한번도 부수지 않았고, 이동하지 않은 경로라면
                        else if (!now.flag && !visited[nx][ny][0]) {
                            q.offer(new Node(nx, ny, now.count + 1, now.flag));
                            visited[nx][ny][0] = true;
                        }
                    } 
                    // 벽일 경우
                    else {
                        // 벽을 한번도 부수지 않았고, 이동하지 않은 경로라면
                        if (!now.flag && !visited[nx][ny][0]) {
                            q.offer(new Node(nx, ny, now.count + 1, true));
                            visited[nx][ny][1] = true;
                        }
                    }

                }
            }
        }
    }

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

        board = new int[n + 1][m + 1];
        visited = new boolean[n + 1][m + 1][2];

        for (int i = 1; i <= n; i++) {
            String str = br.readLine();
            for (int j = 1; j <= m; j++)
                board[i][j] = str.charAt(j - 1) - '0';

        }

        // 0은 이동 , 1은 벽 . 한 번 벽을 깰 수 있다.
        bfs();
        System.out.println(result == Integer.MAX_VALUE ? -1 : result);
    }
}