[BaekJoon] 2206번 - 벽 부수고 이동하기 [Java][C++]

문제 링크

---

1. 문제 풀이

$(1,\ 1)$ 에서 $(N,\ M)$ 까지 이동하는 최단 거리를 구하되 벽을 한번은 부술 수 있는 문제로 기본적으로 최단 거리 BFS를 활용하되 특정 좌표를 벽을 부순 적이 있는 상태로 방문했는지, 벽을 부순 적이 없는 채로 방문했는지 상태까지 검증하면 된다. 이를 위해 방문 체크 배열을 3차원으로 설정해서 좌표와 벽을 부순 횟수까지 3가지 파라미터에 대한 방문 체크를 해줬다.

---

2. 코드

1. 풀이 [Java]

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;

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

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

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

    static int bfs() {
        Queue<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{0, 0, 0});

        boolean[][][] visited = new boolean[n][m][2];
        visited[0][0][0] = true;

        int dist = 1;

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

            while (size-- > 0) {
                int[] node = q.poll();
                if (node[0] == n - 1 && node[1] == m - 1) return dist;

                for (int d = 0; d < 4; d++) {
                    int nr = node[0] + dr[d];
                    int nc = node[1] + dc[d];

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

                    if (grid[nr][nc] == '0') {
                        if (visited[nr][nc][node[2]]) continue;

                        q.offer(new int[]{nr, nc, node[2]});
                        visited[nr][nc][node[2]] = true;
                    } else {
                        if (node[2] > 0) continue;
                        if (visited[nr][nc][node[2] + 1]) continue;

                        q.offer(new int[]{nr, nc, node[2] + 1});
                        visited[nr][nc][node[2] + 1] = true;
                    }
                }
            }

            dist++;
        }

        return -1;
    }
}

2. 풀이 [C++]

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

int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};
int n, m;
char grid[1001][1001];
bool visited[1001][1001][2];

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

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

    visited[0][0][0] = true;

    int dist = 1;

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

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

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

            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 (visited[nr][nc][x]) continue;

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

                    q.push({nr, nc, x + 1});
                    visited[nr][nc][x + 1] = true;
                }
            }
        }

        dist++;
    }

    return -1;
}

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

    cin >> n >> m;

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

    cout << bfs();
}

---