[BOJ] 2583번 : 영역 구하기

1. problem : 

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

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int m, n, k; 
int board[105][105];
vector<int> v; 
int cnt;
queue<pair<int, int>> Q; 
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> m >> n >> k;
	while (k--) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		for (int i = b; i < d; i++) {
			for (int j = a; j < c; j++) {
				board[i][j] = 1;
			}
		}
	}
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (board[i][j]) continue;
			cnt++;
			int max_val = 1;
			board[i][j] = 1;
			Q.push({ i,j });
			while (!Q.empty()) {
				pair<int, int> cur = Q.front(); Q.pop();
				for (int dir = 0; dir < 4; dir++) {
					int nx = cur.X + dx[dir];
					int ny = cur.Y + dy[dir];
					if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
					if (board[nx][ny] >= 1) continue;
					max_val++;
					board[nx][ny] = max_val;
					Q.push({ nx,ny });
				}
			}
			v.push_back(max_val);
		}
	}
	cout << cnt << '\n';
	sort(v.begin(), v.end());
	for (int i = 0; i < v.size(); i++) cout << v[i] << ' ';
}

bfs를 이용해 풀었다. max_val을 설정해서, 0인 칸을 찾을 때마다, ++을 해주었다. while문이 끝나고 나서, vector에 max_val을 push 해주었다. 

 

3. solution 2 :

// Authored by : 0silver00
// Co-authored by : BaaaaaaaaaaarkingDog
// http://boj.kr/d0c205b6ead644d896fec013b6e64129
#include <bits/stdc++.h>
using namespace std;

#define X first
#define Y second
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
int m, n, k;
int board[102][102];
int vis[102][102];

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> m >> n >> k;
  while (k--) {
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    for (int j = y1; j < y2; j++)
      for (int k = x1; k < x2; k++)
        board[j][k] = 1;
  }

  int count = 0;
  vector<int> ans;
	
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
      if (board[i][j] == 1 || vis[i][j] == 1)
        continue;
      queue<pair<int, int>> Q;
      vis[i][j] = 1;
      Q.push({ i, j });
      int width = 1;
      count++;
      while (!Q.empty()) {
        auto cur = Q.front();
        Q.pop();
        for (int dir = 0; dir < 4; dir++) {
          int nx = cur.X + dx[dir];
          int ny = cur.Y + dy[dir];
          if (nx < 0 || nx >= m || ny < 0 || ny >= n)
            continue;
          if (board[nx][ny] == 1 || vis[nx][ny] == 1)
            continue;
          Q.push({ nx, ny });
          vis[nx][ny] = 1;
          width++;
        }
      }
      ans.push_back(width);
    }
  }
  sort(ans.begin(), ans.end());

  cout << count << '\n';
  for (int i : ans)
    cout << i << ' ';

  return 0;  
}

source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x09/solutions/2583.cpp

basic-algo-lecture/0x09/solutions/2583.cpp at master · encrypted-def/basic-algo-lecture

이 코드에서는 vis 배열을 두어, 본 배열인 board는  바꾸지 않으면서, bfs를 진행했다.