[BOJ] 16946 - 벽 부수고 이동하기 4

https://www.acmicpc.net/problem/16946

BOJ = 벽 부수고 이동하기 4

문제 유형: bfs

시간 제한: 2초

메모리 제한: 512MB

 

문제

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 변을 공유할 때, 인접하다고 한다.

각각의 벽에 대해서 다음을 구해보려고 한다.

• 벽을 부수고 이동할 수 있는 곳으로 변경한다.
• 그 위치에서 이동할 수 있는 칸의 개수를 세어본다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

 

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다.

 

출력

맵의 형태로 정답을 출력한다. 원래 빈 칸인 곳은 0을 출력하고, 벽인 곳은 이동할 수 있는 칸의 개수를 10으로 나눈 나머지를 출력한다.

 

풀이

컴포넌트의 크기를 저장하는 배열과 셀이 소속된 컴포넌트를 저장하는 2D배열을 만든다.

우선 mat의 값이 0인 인접한 셀들에 대해 컴포넌트로 묶고 크기를 저장한다. 각 셀들에 컴포넌트 ID를 DBMS의 auto_increment처럼 부여한다. 그리고 컴포넌트 크기배열에 컴포넌트 ID번 인덱스에 크기가 저장되도록 하였다. 벽은 컴포넌트 0번에 소속되게 하였다.

 

이제 프리컴퓨트가 끝나고, mat값이 1인 셀들은 인접한 컴포넌트들을 조사한다. 인접한 컴포넌트들의 크기만큼 더하고 mod 10을 해준값을 저장한다.

 

변환된 행렬을 출력해주면 된다.

 

코드

C++

#include <bits/stdc++.h>
#define pii pair<int, int>

using namespace std;

int n, m;

int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

int bfs(int r, int c, int componentID, vector<vector<int>> &mat,
        vector<vector<int>> &visited) {
  queue<pii> q;
  q.push({r, c});
  visited[r][c] = componentID;
  int componentSize = 0;

  while (!q.empty()) {
    auto curr = q.front();
    int x = curr.first;
    int y = curr.second;
    q.pop();
    componentSize++;

    for (int i = 0; i < 4; ++i) {
      int nx = x + dx[i];
      int ny = y + dy[i];

      if (nx < 0 || ny < 0 || nx >= n || ny >= m || mat[nx][ny] == 1 ||
          visited[nx][ny] == componentID)
        continue;
      visited[nx][ny] = componentID;
      q.push({nx, ny});
    }
  }

  return componentSize;
}

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  cin >> n >> m;
  vector<vector<int>> mat(n, vector<int>(m));
  vector<vector<int>> visited(n, vector<int>(m, 0));
  vector<int> componentSizes = {-1};
  for (int i = 0; i < n; ++i) {
    string s;
    cin >> s;
    for (int j = 0; j < m; ++j) {
      mat[i][j] = s[j] - '0';
    }
  }

  // precompute area size..
  int componentID = 1;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      if (mat[i][j] == 0 && visited[i][j] == 0) {
        int size = bfs(i, j, componentID, mat, visited);
        componentSizes.emplace_back(size);
        componentID++;
      }
    }
  }

  // modify mat..
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      if (mat[i][j] != 0) {
        unordered_set<int> adjComponents;
        for (int k = 0; k < 4; ++k) {
          int nx = i + dx[k];
          int ny = j + dy[k];
          if (nx < 0 || ny < 0 || nx >= n || ny >= m || visited[nx][ny] == 0)
            continue;
          adjComponents.insert(visited[nx][ny]);
        }
        for (const auto &component : adjComponents) {
          mat[i][j] += componentSizes[component];
        }
        mat[i][j] %= 10;
      }
      cout << mat[i][j];
    }
    cout << "\n";
  }

  return 0;
}