[C++] 백준 2234번 성곽

비트마스킹 문제입니다.

왼쪽에 벽 - 1
위쪽에 벽 - 2
오른쪽 벽 - 4
아래에 벽 - 8

11의 경우
1 + 2 + 8로
왼쪽, 위쪽, 아래에 벽이 있는 경우입니다.

BFS를 이용해서 각 지점에서 출발을 합니다.
비트마스킹을 통해 벽이 있는지 확인을 하고 해당하는 부분들을 영역처리합니다.
영역의 개수와 영역의 크기를 출력합니다. (1, 2)
마주하는 영역의 경우 크기를 합쳐서 가장 크게 합칠 수 잇는 값을 출력합니다. (3)

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

vector<vector<int>> v;
int visit[51][51];
int roomSize[2501];
int n, m;

void bfs(int a, int b, int c)
{
  queue<pair<int, int>> q;
  q.push(make_pair(a, b));
  visit[a][b] = c;

  while (!q.empty())
  {
    int y = q.front().first;
    int x = q.front().second;
    roomSize[c] += 1;
    q.pop();

    if (!(v[y][x] & 1) && visit[y][x - 1] == 0)
    {
      q.push(make_pair(y, x - 1));
      visit[y][x - 1] = c;
    }
    if (!(v[y][x] & 2) && visit[y - 1][x] == 0)
    {
      q.push(make_pair(y - 1, x));
      visit[y - 1][x] = c;
    }
    if (!(v[y][x] & 4) && visit[y][x + 1] == 0)
    {
      q.push(make_pair(y, x + 1));
      visit[y][x + 1] = c;
    }
    if (!(v[y][x] & 8) && visit[y + 1][x] == 0)
    {
      q.push(make_pair(y + 1, x));
      visit[y + 1][x] = c;
    }
  }
}

int main(int argc, char *argv[])
{
  int c = 0;
  int num;
  int maxSizeRoom = 0;
  int newSizeRoom = 0;

  cin >> n;
  cin >> m;

  memset(visit, 0, sizeof(visit));
  memset(roomSize, 0, sizeof(roomSize));

  for (int i = 0; i < m; ++i)
  {
    vector<int> temp;
    for (int j = 0; j < n; ++j)
    {
      cin >> num;
      temp.push_back(num);
    }
    v.push_back(temp);
    temp.clear();
  }

  for (int i = 0; i < m; ++i)
  {
    for (int j = 0; j < n; ++j)
    {
      if (visit[i][j] != 0)
      {
        continue;
      }
      ++c;
      bfs(i, j, c);
    }
  }

  for (int i = 0; i <= c; ++i)
  {
    maxSizeRoom = max(maxSizeRoom, roomSize[i]);
  }

  newSizeRoom = maxSizeRoom;

  for (int i = 0; i < m; ++i)
  {
    for (int j = 0; j < n; ++j)
    {
      if (i - 1 >= 0 && visit[i][j] != visit[i - 1][j])
      {
        newSizeRoom = max(newSizeRoom, roomSize[visit[i][j]] + roomSize[visit[i - 1][j]]);
      }
      if (j - 1 >= 0 && visit[i][j] != visit[i][j - 1])
      {
        newSizeRoom = max(newSizeRoom, roomSize[visit[i][j]] + roomSize[visit[i][j - 1]]);
      }
      if (i + 1 < m && visit[i][j] != visit[i + 1][j])
      {
        newSizeRoom = max(newSizeRoom, roomSize[visit[i][j]] + roomSize[visit[i + 1][j]]);
      }
      if (j + 1 >= n && visit[i][j] != visit[i][j + 1])
      {
        newSizeRoom = max(newSizeRoom, roomSize[visit[i][j]] + roomSize[visit[i][j + 1]]);
      }
    }
  }

  cout << c << endl;
  cout << maxSizeRoom << endl;
  cout << newSizeRoom << endl;

  return 0;
}