[BaekJoon] #16933 - 벽 부수고 이동하기 3 [Java][C++]

문제 링크

---

1. 아이디어

BaekJoon 14442번 - 벽 부수고 이동하기 2 문제에서 낮과 밤이 추가되어 벽은 낮에만 부술 수 있으며 이동하지 않고 머물 수도 있는 문제로 방문 체크에서 낮과 밤도 상태로 추가하면 된다. 탐색 중 벽을 만나면 낮일 경우 동일하게 풀고 밤일 경우 flag를 true로 설정해서 이동하지 않는 경우를 고려했다.

---

2. 복잡도

접근	시간	공간
풀이	$O(K \times N \times M)$	$O(K \times N \times M)$

($N$ = 입력값 n, $M$ = 입력값 m, $K$ = 입력값 k)

---

3. 코드

풀이 [Java][C++]

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

public class Main {

    static int[] dr = {-1, 0, 1, 0};
    static int[] dc = {0, 1, 0, -1};
    static int n, m;
    static char[][] grid;

    static class Node {
        int r, c;
        int x;
        int day;  // 낮=0, 밤=1

        public Node(int r, int c, int x, int day) {
            this.r = r;
            this.c = c;
            this.x = x;
            this.day = day;
        }
    }

    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());
        int k = Integer.parseInt(st.nextToken());

        grid = new char[n][m];
        for (int i = 0; i < n; i++) {
            grid[i] = br.readLine().toCharArray();
        }

        System.out.println(bfs(k));
    }

    static int bfs(int k) {
        Queue<Node> q = new ArrayDeque<>();
        q.offer(new Node(0, 0, 0, 0));

        boolean[][][][] vis = new boolean[n][m][1 + k][2];
        vis[0][0][0][0] = true;

        int dist = 1;

        while (!q.isEmpty()) {
            int sz = q.size();

            while (sz-- > 0) {
                Node cur = q.poll();
                if (cur.r == n - 1 && cur.c == m - 1) return dist;

                boolean flag = false;
                for (int d = 0; d < 4; d++) {
                    int nr = cur.r + dr[d];
                    int nc = cur.c + dc[d];

                    if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;

                    if (grid[nr][nc] == '0') {
                        if (vis[nr][nc][cur.x][1 - cur.day]) continue;

                        q.offer(new Node(nr, nc, cur.x, 1 - cur.day));
                        vis[nr][nc][cur.x][1 - cur.day] = true;
                    } else {
                        if (cur.day == 0) {
                            if (cur.x >= k) continue;
                            if (vis[nr][nc][cur.x + 1][1 - cur.day]) continue;

                            q.offer(new Node(nr, nc, cur.x + 1, 1 - cur.day));
                            vis[nr][nc][cur.x + 1][1 - cur.day] = true;
                        } else {
                            flag = true;
                        }
                    }
                }

                if (flag) {
                    if (vis[cur.r][cur.c][cur.x][1 - cur.day]) continue;

                    q.offer(new Node(cur.r, cur.c, cur.x, 1 - cur.day));
                    vis[cur.r][cur.c][cur.x][1 - cur.day] = true;
                }
            }

            dist++;
        }

        return -1;
    }
}

#include <bits/stdc++.h>
using namespace std;

const int MAX = 1000 + 1;
int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};
int n, m, k;
char grid[MAX][MAX];
bool vis[MAX][MAX][1 + 10][2];

struct Node {
    int r, c, x, day;
};

int bfs() {
    queue<Node> q;
    q.push({0, 0, 0, 0});

    vis[0][0][0][0] = true;

    int dist = 1;

    while (!q.empty()) {
        int sz = q.size();

        while (sz--) {
            auto [r, c, x, day] = q.front();
            q.pop();

            if (r == n - 1 && c == m - 1) return dist;

            bool flag = false;
            for (int d = 0; d < 4; d++) {
                int nr = r + dr[d];
                int nc = c + dc[d];

                if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;

                if (grid[nr][nc] == '0') {
                    if (vis[nr][nc][x][1 - day]) continue;

                    q.push({nr, nc, x, 1 - day});
                    vis[nr][nc][x][1 - day] = true;
                } else {
                    if (day == 0) {
                        if (x >= k) continue;
                        if (vis[nr][nc][x + 1][1 - day]) continue;

                        q.push({nr, nc, x + 1, 1 - day});
                        vis[nr][nc][x + 1][1 - day] = true;
                    } else {
                        flag = true;
                    }
                }
            }

            if (flag) {
                if (vis[r][c][x][1 - day]) continue;

                q.push({r, c, x, 1 - day});
                vis[r][c][x][1 - day] = true;
            }
        }

        dist++;
    }

    return -1;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m >> k;

    for (int i = 0; i < n; i++) {
        cin >> grid[i];
    }

    cout << bfs();
}

---