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

문제 링크

2206번: 벽 부수고 이동하기

---

요새 프로젝트를 진행한다고 블로그 글을 잘 못쓰네요 😂

그래서 오늘부터 간단하게 벽 부수고 이동하기 문제 시리즈를 진행할 계획입니다.

시리즈는 1부터 4까지 있고, 이번 포스팅부터 시작합니다!

풀이

VST (3중배열) + BFS로 풀이하면 됩니다.

이 문제는 흔하게 볼 수 있는 BFS를 이용한 최단 거리 문제의 응용 버전이라고 볼 수 있겠습니다.

 

보통 최단 거리 문제는 `visit` 배열로 전에 갔던 경로를 체크하여 가지 않는 식으로 갑니다.

(예전에 풀었던 프로그래머스의 리코쳇 로봇 문제가 그 예 중 하나입니다.)

이 문제는 여기서 한발짝 더 나아가, 벽을 한 개까지 부수고 이동하느냐 안하느냐를 따져야 합니다. 이걸 어떻게 따지느냐?

바로 `visit` 배열에 벽을 부수고 이동한 경우와 하지 않은 경우를 모두 저장하는 방법을 사용합니다.

보통`visit` 배열은 \(N\)과 \(M\) 길이의 이중 배열로 체크하고,

이 배열에 (부수는 경우)와 (부수지 않는 경우)의 2가지 경우를 저장하기 위해 삼중 배열을 만들어 체크하면 되겠습니다.

 

풀이코드

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

#define endl "\n"

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

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

  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 == 1) 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 <= 1; 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;
}

이 문제와 비슷한 유형들(DP와 BFS를 합친 유형)이 백준에 종종 보이기 때문에, 풀이 방법을 알아두면 다른 유사한 문제도 잘 풀어나가실 수 있을 겁니다!

 

배운점

• DP와 BFS를 복습할 수 있었습니다

---

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

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