백준 2234번 성곽[C++]

1. 문제 풀이

1-1. 문제 개요

 안녕하세요. 오늘 풀어볼 문제는 백준 2234번 성곽입니다. 문제의 유형은 벽이 있는 2차원 배열에서 각 영역의 넓이를 구하는 flood fill 알고리즘의 응용이었습니다. flood fill의 경우 너비 우선 탐색과 깊이 우선 탐색 중 더 선호하시는 걸 선택하셔도 무방합니다. 저는 너비 우선 탐색을 선택해서 문제를 풀이했습니다.

 

 이 문제는 여러 응용이 필요한 문제이기 때문에 너비 우선 탐색 기법을 사용한 flood fill 알고리즘에 대해서 어느 정도 기초가 필요합니다. 만약 이에 대해서 모르신다면 공부를 하고 기초 문제들을 몇 개 푼 뒤에 시도하는 것을 추천합니다.

 

1-2. 어느 방향이 벽인지 판별하는 방법

 문제에서 주어진 2차원 배열에서 각 칸에는 0부터 15까지의 숫자가 적혀있습니다. 이 숫자는 아래와 같은 조건에 의한 숫자입니다.

 

1. 서쪽에 벽이 있으면 1을 더한다.

2. 북쪽에 벽이 있으면 2를 더한다.

3. 동쪽에 벽이 있으면 4를 더한다.

4. 남쪽에 벽이 있으면 8을 더한다.

 

조건을 통해 어떤 방향이든 벽이 있으면 2의 제곱수를 더하고 있다는 사실을 알 수 있습니다. 우리는 이 숫자들을 10진수로만 본다면 어느 방향이 벽인지 확인하는 것이 어려울 수 있습니다. 하지만 0부터 15를 이진수로 바꿔보면 어느 방향이 벽인지 직관적으로 확인이 가능합니다.

위 그림을 통해 6은 2와 4를 더했고, 북쪽과 동쪽에 벽이 있음을 알 수 있습니다. 10과 14도 그림과 같은 방향에 벽이 있음을 알 수 있습니다.

 

 너비 우선 탐색을 할 때, 각 방향에 대해서 탐색을 할 수 있는 곳인지 판별하는 부분에서 "<<" 와 "&" 등의 비트 연산자를 사용하여 벽을 판별하시면 되겠습니다.

 

// dx[0], dy[0] : 서쪽	dx[1], dy[1] : 북쪽
// dx[2], dy[2] : 동쪽	dx[3], dy[3] : 남쪽
const int dx[4] = { 0, -1, 0, 1 };
const int dy[4] = { -1, 0, 1, 0 };

void BFS(int sx, int sy){
    queue<pair<int,int>> q;
    /*
    *	생략
    */
    auto &[cx, cy] = q.front(); q.pop();
    for(int dir = 0; dir < 4; dir++){
    	int nx = cx + dx[dir];
        int ny = cy + dy[dir];
        // 생략
        
        // ( 1 << dir ) : pow( 2, dir )
        // ex) dir = 2라면 ( 1 << dir ) = 4임
        // board[nx][ny]가 이진수로 0110 이라고 예시를 들면
        // 0110 & 0010 = 0010으로 양수의 결과 나옵니다.
        // 이를 통해서 dir = 2는 동쪽이고 동쪽에 벽이 있음을 알 수 있습니다.
        if( board[nx][ny] & ( 1 << dir )) continue;
        
        // 생략
	}
}

 

1-3. 벽을 하나 제거했을 때, 가장 큰 방의 넓이를 구하는 방법

 벽인지 판별이 가능하면 문제에서 요구하는 방의 개수와 가장 큰 방의 넓이를 구할 수 있습니다. 하지만 벽을 하나 제거 했을 때, 가장 큰 방의 넓이를 구하는 것은 어려울 수 있습니다. 저도 처음엔 그래프 리모델링인 줄 알고 한참 헤매었습니다.

 

 이를 구하기 위해서는 너비 우선 탐색을 진행할 때, 방문 배열에 상태를 부여해 각 칸이 어느 영역인지 표기할 필요가 있습니다.

 

 

 flood fill을 진행하면서 위와 같이 상태를 부여하고 각 영역에 넓이를 배열에 저장한 다음 2차원 배열을 순회하면서 인접한 4방향 중 다른 영역이 있다면 두 영역의 합 중 최댓값을 찾는 방법으로 찾을 수 있습니다.

  int max_area{};
  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
      int cur_idx = vis[i][j];
      for(int dir = 0; dir < 4; dir++){
        int nx = i + dx[dir];
        int ny = j + dy[dir];
        if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
        int nxt_idx = vis[nx][ny];
        if(cur_idx == nxt_idx) continue;
        max_area = max(max_area, ans[cur_idx-1] + ans[nxt_idx-1]);
      }
    }
  }

 

1-4. 시간복잡도 분석

너비 우선 탐색 : O( N * M )

벽을 제거했을 때 가장 큰 방의 넓이 구하기 : O( 4 * N * M )

상수를 제거한 이 구현의 시간복잡도는 O( N * M )이므로 시간 초과 없이 통과할 수 있습니다.

 

1-5. 요약

flood fill 알고리즘의 응용 문제로 각 칸의 숫자를 이진수의 관점으로 보게되면 어느 방향이 벽인지 판별하는 것이 직관적으로 가능하다. "<<"와 "&" 연산자를 사용해 벽을 판별하면서 너비 우선 탐색을 진행하면된다. 벽을 하나 제거했을 때, 가장 큰 방의 넓이를 구하는 방법으로는 방문 배열에 상태를 부여하여 flood fill을 진행하고 각 영역의 넓이를 배열로 저장합니다. 그 다음 방문 배열을 순회하면서 인접한 4방향 중 다른 영역이 있다면, 두 영역의 넓이 합 중 최댓값을 찾아 문제를 해결할 수 있습니다.

 

2. 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti; typedef tuple<ll, ll, ll> tl; typedef vector<int> vi; typedef vector<ll> vl;
typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<ti> vti; typedef vector<tl> vtl;
typedef vector<string> vs; typedef vector<bool> vb;
#define X first
#define Y second
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
const char nl = '\n';
int n, m;
int board[55][55];
int vis[55][55];
const int dx[4] = { 0, -1, 0, 1 };
const int dy[4] = { -1, 0, 1, 0 };
vector<int> ans;
int cnt = 0;
void bfs(int sx, int sy){
  queue<pi> q;
  q.push({sx, sy});
  vis[sx][sy] = cnt;
  int area = 1;
  while(!q.empty()){
    auto &[cx, cy] = q.front(); q.pop();
    for(int dir = 0; dir < 4; dir++){
      int nx = cx + dx[dir];
      int ny = cy + dy[dir];
      if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
      // 벽이 있는 상태
      if(board[cx][cy] & (1 << dir)) continue;
      if(vis[nx][ny]) continue;
      area++;
      vis[nx][ny] = cnt;
      q.push({nx, ny});
    }
  }
  ans.pb(area);
}
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> m >> n;
  for(int i = 0; i < n; i++) for(int j = 0; j < m; j++)
    cin >> board[i][j];
  
  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
      if(vis[i][j]) continue;
      cnt++;
      bfs(i, j);
    }
  }
  int max_area{};
  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
      int cur_idx = vis[i][j];
      for(int dir = 0; dir < 4; dir++){
        int nx = i + dx[dir];
        int ny = j + dy[dir];
        if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
        int nxt_idx = vis[nx][ny];
        if(cur_idx == nxt_idx) continue;
        max_area = max(max_area, ans[cur_idx-1] + ans[nxt_idx-1]);
      }
    }
  }
  cout << cnt << nl << *max_element(ans.begin(), ans.end()) << nl << max_area;
}

 

3. 제출 결과