백준 2234번 성곽 ( C++ )

문제

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

 

해설

커넥티드 컴퍼넌트를 이용한 문제

옆의 집합과 합치는 과정을 신경써야함

 

코드

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int visited[54][54], mp[54][54], ret_cnt, ret_max, ret_max2, n, m, tmp, cnt_room[2504];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
 
int dfs(int y, int x, int cnt_idx)
{
  int cnt = 1;
  visited[y][x] = cnt_idx;
  for (int i = 0; i < 4; i++)
  {
    if (!(mp[y][x] & (1 << i)))
    {
      int ny = y + dy[i];
      int nx = x + dx[i];
      if (ny >= 0 && ny < (m) && nx >= 0 && nx < n && visited[ny][nx] == 0)
      {
        cnt += dfs(ny, nx, cnt_idx);
      }
    }
  }
  return cnt;
}
 
// mp값이 1인곳은 벽 or 못가는곳  // 0인 곳은 갈 수 있는 곳
int main()
{
  cin >> n >> m;
  for (int i = 0; i < m; i++)
  {
    for (int j = 0; j < n; j++)
    {
      cin >> mp[i][j];
    }
  }
 
  for (int i = 0; i < (m); i++)
  {
    for (int j = 0; j < (n); j++)
    {
      if (visited[i][j] == 0)
      {
        ret_cnt++;
        int cnt = dfs(i, j, ret_cnt);
        ret_max = max(cnt, ret_max);
        cnt_room[ret_cnt] = cnt;
      }
    }
  }
 
  for (int i = 0; i < m; i++)
  {
    for (int j = 0; j < n; j++)
    {
      if (j + 1 < n)
      {
        int a = visited[i][j];
        int b = visited[i][j + 1];
        if (a != b)
        {
          ret_max2 = max(ret_max2, cnt_room[a] + cnt_room[b]);
        }
      }
      if (i + 1 < m)
      {
        int a = visited[i][j];
        int b = visited[i + 1][j];
        if (a != b)
        {
          ret_max2 = max(ret_max2, cnt_room[a] + cnt_room[b]);
        }
      }
    }
  }
  cout << ret_cnt << "\n"
       << ret_max << "\n"
       << ret_max2;
}