[백준] 14442번: 벽 부수고 이동하기 2 (C++)

문제 링크

14442번: 벽 부수고 이동하기 2

---

저번에 작성했던 벽 부수고 지나가기 첫 문제 포스팅에 이어 두번째 문제입니다.

이번 문제는 첫번째 문제에서 조건 하나만 변경한 문제이니, 그렇게 차이는 나지 않습니다!

풀이해보겠습니다~

풀이

이전 문제와 마찬가지로 VST(3중배열) + BFS로 풀이하면 됩니다.

대신 이전 문제는 2개까지만 벽을 부수는 것을 허용했지만, 이번 문제는 10개까지 벽을 부술 수 있습니다.

따라서 그만큼 VST배열의 크기를 늘려서 저장하고,

저장한 배열을 방문 용도 + 경우의 수 저장 용도로 사용하면서 거리를 측정해주면 되겠습니다!

풀이코드

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

#define endl "\n"

int mp[1001][1001];
int vst[11][1001][1001];
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

void solve() {
  int n, m, k;
  cin >> n >> m >> k;

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

  queue<tuple<int,int,int>> Q;
  Q.push({0, 0, 0});
  vst[0][0][0] = 1;
  while (!Q.empty()) {
    auto [b, x, y] = Q.front(); Q.pop();

    for (int d = 0; d < 4; d++) {
      int nb = b + 1;
      int nx = x + dx[d];
      int ny = y + dy[d];

      if (nx < 0 or nx >= n or ny < 0 or ny >= m) continue;
      if (vst[b][nx][ny]) continue;
      if (mp[nx][ny]) {
        if (b == k) continue;
        if (vst[nb][nx][ny]) continue;
        vst[nb][nx][ny] = vst[b][x][y] + 1;
        Q.push({nb, nx, ny});
      } else {
        vst[b][nx][ny] = vst[b][x][y] + 1;
        Q.push({b, nx, ny});
      }
    }
  }

  int res = 1e9;
  for (int b = 0; b <= k; b++) {
    int dis = vst[b][n - 1][m - 1];
    if (dis == 0) continue;
    res = min(res, dis);
  }
  if (res == 1e9) cout << -1;
  else cout << res;
}

int main() {
#ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#else
  ios_base::sync_with_stdio(false);
  cin.tie(0);
#endif
  solve();
  return 0;
}

---

부족한 글 봐주셔서 감사합니다. 🙇

풀이와 코드에 부족한 점이나 추가하면 좋을 점이 있으면 댓글 주세요!