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

문제 링크

16946번: 벽 부수고 이동하기 4

---

이번 문제는 이전 벽 부수고 이동하기 시리즈 1~3과는 조금 다릅니다.

이전 문제들은 벽을 부수고 지나가면서 최단 경로를 구하는 문제였지만,

이번 4번째 문제는 벽을 부수고 이동할 수 있는 칸의 개수를 세어보는 경우의 수 문제로 바뀌었습니다.

이번 문제는 풀면서 저도 우여곡절이 살짝 있었기에, 그런 우여곡절들을 공유하면서 풀이해보겠습니다.

풀이

DFS로 풀이했습니다. (BFS도 가능)

보통 경우의 수는 백트래킹으로 풀이하는데, 백트래킹을 주로 DFS를 사용하는 것에서 착안해서 DFS로 접근했습니다.

BFS로도 풀 수 있겠지만, DFS를 적용하기 위해 재귀로 풀다보니 조금 직관적?이어서 꿋꿋하게 DFS로 풀었습니다.

이 문제를 처음 보면 출력이 잘 이해가 되지 않을 수 있는데, 찬찬히 생각해보면 다음과 같이 값이 표현된다는 사실을 알 수 있습니다.

위 그림처럼 벽이 없어지는 칸을 포함해서 이동할 수 있는 부분(0인 부분)의 수를 세어주면 되겠습니다.

여기서 주의!할 점은 이동 가능한 칸 수를 10으로 나누어서 표현해야 한다는 점입니다. 제가 그걸 안해서 틀렸었습니다.

칸 수를 세는 방법이 DFS도 가능하지만, BFS도 가능하기 때문에 자신에게 알맞은 방법을 사용해서 세어주면 되겠습니다.

 

하지만 칸만 세어서 문제가 풀리면 괜히 정답률이 25%(글 작성하는 현재 정답률) 아니겠죠? 또 문제가 있습니다.

바로 일반적인 방법으로 수를 세면 시간초과가 납니다. 왜냐하면 \(1000*1000\)의 배열에서 최악의 경우 이동가능한 칸 수를 50만 개의 벽에서 세는 경우가 있을 수 있기 때문에, \(1,000*1,000*500,000\)이라는 시간복잡도가 발생하죠.

그렇기 때문에 빈칸을 여러번 세지 않도록 최적화를 해줘야한다는 점도 이 문제의 포인트 중 하나입니다.

저는 \(vst\) 배열과 \(num\)배열을 이용해서 최적화를 진행했습니다. 각 배열의 용도는 다음과 같습니다.

• \(vst[N][M]\) : 해당 인덱스에 위치한 칸(좌표)의 그룹
• \(num[NM]\) : 해당 인덱스에 위치한 칸(좌표)에서 이동 가능한 칸 수

(num이 1차원 배열인 이유는, DFS에서 2차원 좌표 계산 없이 편하게 값을 넣기 위함입니다.)

이동 가능한 칸 수를 구하고 나면, \(num\) 배열의 정보를 이용해서 결과값을 도출하면 되겠습니다.

벽이 있을 때 상하좌우를 검사해서 \(vst\)에 저장한 그룹 값을 `set`으로 저장해서 같은 값을 더하지 않도록 방지한 다음, `set`에 남은 \(num\) 배열 인덱스들의 값들을 더해주면 되겠습니다.

(말이 어려울 수 있으니 코드를 참고해주세요!)

풀이코드

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

#define endl "\n"

int n, m;
string mp[1001];
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
int vst[1001][1001];
int num[1001 * 1001];

void dfs(int x, int y, int idx) {
  vst[x][y] = idx;
  num[idx]++;
  for (int d = 0; d < 4; d++) {
    int nx = x + dx[d];
    int ny = y + dy[d];

    if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
    if (vst[nx][ny] || mp[nx][ny] == '1') continue;
    dfs(nx, ny, idx);
  }
}

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

  for (int i = 0; i < n; i++) {
    cin >> mp[i];
  }

  int idx = 1;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if (mp[i][j] == '1' || vst[i][j]) continue;
      
      dfs(i, j, idx++);
    }
  }

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if (mp[i][j] == '0') {
        cout << 0;
        continue;
      }

      int cnt = 1;
      set<int> s;
      for (int d = 0; d < 4; d++) {
        int nx = i + dx[d];
        int ny = j + dy[d];

        if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
        if (mp[nx][ny] == '1') continue;
        s.insert(vst[nx][ny]);
      }
      for (int k : s) cnt += num[k];
      cout << cnt % 10;
    }
    cout << endl;
  }
}

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;
}

 

배운점

• 그룹으로 묶어서 최적화하는 방식을 배웠습니다.

---

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

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