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

문제 링크

16933번: 벽 부수고 이동하기 3

---

링크 : 벽 부수고 이동하기 1

링크 : 벽 부수고 이동하기 2

 

벽 부수고 이동하기 1과 2에 이어서 3번 문제입니다!

이번 문제도 저번 문제들의 연장선에 있습니다. 저번 문제에서 낮과 밤이 추가됐죠!

이번 문제도 한번 풀어보겠습니다~

풀이

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

이전 문제의 DP는 \(k\)(벽을 부술 수 있는 한도)와 \(n, m\)(맵의 행렬 길이)로 풀 수 있었습니다.

이번 3번째 문제는 이전 벽 부수고 이동하기 2에 이어서 낮과 밤이 번갈아가는 부분이 추가되었습니다.

낮과 밤이 번갈아가는 부분을 \(day\)라고 정하면, 저장하면서 BFS를 진행할 \(VST\) 배열은 다음과 같이 표현됩니다.

\[VST \ [day][k][n][m]\]

위 배열에 값을 저장하면 되는데, 문제는 밤에만 벽을 넘을 수 있다는 조건입니다.

이 조건은 "현재 상태가 낮이 아니라 밤일 때 벽을 넘을 수 있다"는 의미이므로,

\(day\)가 밤일 경우에 벽을 넘는 경우를 큐에 추가해주면 되겠습니다!

저는 \(day\)가 0일 때 낮, 1일 때 밤으로 정해놓고 풀이를 진행했습니다.

풀이코드

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

#define endl "\n"

int mp[1001][1001];
int vst[2][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,int>> Q;
  Q.push({0, 0, 0, 0});
  vst[0][0][0][0] = 1;
  while (!Q.empty()) {
    auto [day, b, x, y] = Q.front(); Q.pop();

    for (int d = 0; d < 4; d++) {
      int nday = !day;
      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 (mp[nx][ny]) {
        if (day) {
          if (!vst[nday][b][x][y]) {
            vst[nday][b][x][y] = vst[day][b][x][y] + 1;
            Q.push({nday, b, x, y});
          }
          continue;
        }
        if (b == k) continue;
        if (vst[nday][nb][nx][ny]) continue;
        vst[nday][nb][nx][ny] = vst[day][b][x][y] + 1;
        Q.push({nday, nb, nx, ny});
      } else {
        if (vst[nday][b][nx][ny]) continue;
        vst[nday][b][nx][ny] = vst[day][b][x][y] + 1;
        Q.push({nday, b, nx, ny});
      }
    }
  }
  
  int res = 1e9;
  for (int day = 0; day < 2; day++) {
    for (int b = 0; b <= k; b++) {
      int dis = vst[day][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;
}

 

---

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

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