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

 

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

---

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

문제 설명:

N×M 크기의 격자 지도에서 최단 경로로 (0,0)에서 (N-1,M-1)로 이동하고자 합니다. 이동 중 최대 K개의 벽을 부술 수 있으며, **낮에는 벽을 부수고 이동 가능하지만 밤에는 벽을 부술 수 없습니다.**
또한, 벽이 있는 곳은 부수지 않으면 지나갈 수 없습니다. 이동은 상하좌우로 가능하며, 한 칸을 이동하는 데 1초가 걸립니다.

---

문제 해결 코드

// 벽 부수고 이동하기 3 - BFS + 낮밤 판별
#include <iostream>
#include <queue>
#include <string>
using namespace std;

int n, m, k;
int arr[1001][1001];               // 지도 정보 (0: 빈칸, 1: 벽)
int visited[1001][1001][11];       // 방문 배열: [x][y][벽 부순 횟수]
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
int minAns = 1e9;

// 큐 요소: ((x, y), (남은 벽, 현재 시간)), 낮밤 여부(0: 낮, 1: 밤)
queue<pair<pair<pair<int, int>, pair<int, int>>, int>> q;

void bfs(int x, int y, int remain, int time) {
    q.push({{{x, y}, {remain, time}}, 0});
    visited[x][y][remain] = time;

    while (!q.empty()) {
        auto [info, isNight] = q.front(); q.pop();
        int cx = info.first.first;
        int cy = info.first.second;
        int curRemain = info.second.first;
        int curTime = info.second.second;

        for (int d = 0; d < 4; d++) {
            int nx = cx + dx[d];
            int ny = cy + dy[d];
            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;

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

            // 벽일 경우
            if (arr[nx][ny] == 1) {
                if (curRemain > 0) {
                    if (isNight == 0) { // 낮에는 벽 부수기 가능
                        if (visited[nx][ny][curRemain - 1] == 0 || visited[nx][ny][curRemain - 1] > curTime + 1) {
                            visited[nx][ny][curRemain - 1] = curTime + 1;
                            q.push({{{nx, ny}, {curRemain - 1, curTime + 1}}, 1});
                        }
                    } else { // 밤이면 벽 못 부수고 제자리 대기
                        q.push({{{cx, cy}, {curRemain, curTime + 1}}, 0});
                    }
                }
            }
            // 빈칸일 경우
            else {
                if (visited[nx][ny][curRemain] == 0 || visited[nx][ny][curRemain] > curTime + 1) {
                    visited[nx][ny][curRemain] = curTime + 1;
                    q.push({{{nx, ny}, {curRemain, curTime + 1}}, 1 - isNight});
                }
            }
        }
    }
}

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 == 1e9 ? -1 : minAns) << '\n';
}

---

코드 설명

낮과 밤을 구분하여 벽을 부술 수 있는 조건을 달리하며 BFS를 수행합니다.

• 핵심 알고리즘: BFS (상태: (x, y, 남은벽수, 낮/밤))
• 구현 세부사항:
  • visited[x][y][k]: (x, y)에 벽 k개 남기고 도달한 시간
  • isNight: 짝수 시간은 낮(0), 홀수 시간은 밤(1)
  • 벽이 있을 경우, 낮이면 부수고 진행 가능, 밤이면 대기해야 함
• 시간 복잡도 분석:
  • 상태 공간: O(n ⋅ m ⋅ k)
  • BFS 탐색: O(n ⋅ m ⋅ k), 최악의 경우도 충분히 통과 가능

---

결과

예시 입력:

5 5 10
01100
01010
01010
01010
00110

예시 출력:

9

낮밤과 벽 부수기 조건을 정확히 구현해야 풀 수 있는 시뮬레이션 문제입니다. 다른 아이디어나 개선 사항이 있다면 댓글로 공유해주세요!