백준 2583번 : 영역 구하기

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

2583번: 영역 구하기

 

이 문제는 그래프 탐색 문제이고 DFS, BFS 둘다 이용해서 풀었다.

1.DFS 를 이용한 풀이

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int nmSheet[101][101];
bool check[101][101];
int m, n;
int cnt=0;

void dfs(int a, int b) {
    if (check[a][b] == true) {
        return;
    }
    if (nmSheet[a][b] != 0) {
        return;
    }
    check[a][b] = true;
    cnt++;
    if (a - 1 >= 0 && nmSheet[a - 1][b] == 0 && check[a - 1][b] == false) {  //아래 한칸 탐색
        dfs(a - 1, b);
    }
    if (a + 1 < m && nmSheet[a + 1][b] == 0 && check[a + 1][b] == false) {  // 위 한칸 탐색
        dfs(a + 1, b);
    }
    if (b - 1 >= 0 && nmSheet[a][b - 1] == 0 && check[a][b - 1] == false) {     //왼쪽 한칸 탐색
        dfs(a, b - 1);
    }
    if (b + 1 < n && nmSheet[a][b + 1] == 0 && check[a][b + 1] == false) {   //오른쪽 한칸 탐색
        dfs(a, b + 1);
    }

}
int main() {
    vector<int> ans;
    int k;
    cin >> m >> n >> k;
    while (k--) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        for (int y = y1; y < y2; y++) {
            for (int x = x1; x < x2; x++) {
                nmSheet[y][x] = 1;
                check[y][x] = true;
            }
        }
    }
    for (int i = 0; i < m; i++) {
        for (int k = 0; k < n; k++) {
            if (check[i][k] == false && nmSheet[i][k] == 0) {
                dfs(i, k);
                if (cnt != 0) {
                    ans.push_back(cnt);
                    cnt = 0;
                }
            }
        }
    }
    int len = ans.size();
    sort(ans.begin(), ans.end());
    cout << len << '\n';
    for (int i = 0; i < len; i++) {
        cout << ans[i] << ' ';
    }

}

2.BFS 풀이

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> pii;

int n, m, k, a, c, b, d;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int arr[101][101];
bool check[101][101];
int bfs(int x, int y) {
	int cnt = 0;
	queue<pii> q;
	q.push(pii(x, y));
	check[x][y] = true;
	while (!q.empty()) {
		x = q.front().first;
		y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx >= 0 && nx < n && ny < m && ny>=0) {
				if (!check[nx][ny] && arr[nx][ny] != -1) {
					q.push(pii(nx, ny));
					check[nx][ny]=true;
				}
			}
		}
		cnt++;
	}
	return cnt;

}
int main() {
	cin >> n >> m >> k;
	while (k--) {
		cin >> a >> b >> c >> d;
		for (int y = b; y < d; y++) {
			for (int x = a; x < c; x++) {
				arr[y][x] = -1;
			}
		}
	}
	vector<int> ans;
	for (int i = 0; i < n; i++) {
		for (int s = 0; s < m; s++) {
			if (check[i][s] == false && arr[i][s] != -1) {
				ans.push_back(bfs(i, s));
			}
		}
	}
	sort(ans.begin(), ans.end());
	int len = ans.size();
	cout << len << '\n';
	for (int i = 0; i < len; i++) {
		cout << ans[i]<<" ";
	}
	
	
}