백준 14442번 [벽 부수고 이동하기 2](C++) -yes6686- 티스토리

 

백준 문제 풀이: 14442 (벽 부수고 이동하기 2)

---

문제 링크: https://www.acmicpc.net/problem/14442

문제 설명:

N×M 크기의 이차원 배열로 주어진 맵에서 최단 경로로 (0, 0)에서 (N-1, M-1)까지 이동해야 합니다.
이때, 최대 K개의 벽을 부수고 이동할 수 있습니다. 벽을 부순 상태와 부수지 않은 상태를 구분하여 탐색하는 것이 핵심입니다.
벽을 부수는 횟수에 따라 상태가 다르기 때문에 3차원 visited 배열이 필요합니다.

---

문제 해결 코드

// 벽 부수고 이동하기 2 - BFS + 상태 추적
#include <iostream>
#include <queue>
#include <string>
using namespace std;

int arr[1001][1001];               // 맵 정보
int visited[1001][1001][11];      // 방문 여부 [x][y][남은 벽 부수기]
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
int n, m, k;
int minAns = 1000001;

// 상태: (x, y), 남은 벽 부수기, 이동 거리
void bfs(int x, int y, int wall, int dist) {
    queue<pair<pair<int, int>, pair<int, int>>> q;
    q.push({{x, y}, {wall, dist}});
    visited[x][y][wall] = 1;

    while (!q.empty()) {
        auto [pos, state] = q.front(); q.pop();
        int cx = pos.first, cy = pos.second;
        int cw = state.first, cd = state.second;

        for (int i = 0; i < 4; i++) {
            int nx = cx + dx[i];
            int ny = cy + dy[i];

            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;

            if (nx == n - 1 && ny == m - 1) {
                minAns = min(minAns, cd + 1);
                continue;
            }

            if (arr[nx][ny] == 1 && cw > 0 && !visited[nx][ny][cw - 1]) {
                visited[nx][ny][cw - 1] = 1;
                q.push({{nx, ny}, {cw - 1, cd + 1}});
            }

            if (arr[nx][ny] == 0 && !visited[nx][ny][cw]) {
                visited[nx][ny][cw] = 1;
                q.push({{nx, ny}, {cw, cd + 1}});
            }
        }
    }
}

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

    cin >> n >> m >> k;
    for (int i = 0; i < n; i++) {
        string s; cin >> s;
        for (int j = 0; j < m; j++) {
            arr[i][j] = s[j] - '0';
        }
    }

    if (n == 1 && m == 1) {
        cout << 1 << '\n';
        return 0;
    }

    bfs(0, 0, k, 1);

    cout << (minAns == 1000001 ? -1 : minAns) << '\n';
}

---

코드 설명

BFS를 이용해 최단 경로를 탐색하며, 벽을 부순 횟수를 상태로 같이 저장합니다.

• 핵심 알고리즘: BFS + 상태 공간 확장 (벽 부수기 개수별로 분리)
• 구현 세부사항:
  • visited[x][y][k]: (x, y) 지점에서 벽을 k번 남기고 도달한 여부
  • 벽이 있는 곳에 도달 시, 남은 벽 부수기가 있다면 k-1로 이동
  • 도착 지점 (n-1, m-1) 에 도달하면 minAns 갱신
• 시간 복잡도 분석:
  • O(n ⋅ m ⋅ k): 각각의 위치와 벽 부수기 상태마다 방문 여부 기록

---

결과

예시 입력:

6 4 1
0100
1110
1000
0000
0111
0000

예시 출력:

15

벽을 한 번까지 부술 수 있을 때, 최단거리로 도달 가능한 경우를 탐색합니다.

상태 공간이 늘어나는 BFS 문제에 익숙해지는 데 좋은 예제입니다. 다른 최적화 아이디어가 있다면 댓글로 공유해주세요!