백준 2583 / 영역 구하기

처음엔 그림에 나와있는대로 빈공간은 0, 종이구간은 1인 배열을 만들어 풀어보려고 했다.

온갖 테스트케이스를 넣어봐도 정답이 나왔지만 제출하니 계속 '틀렸습니다'.

어디서 틀린건지 찾느라 시간 많이썼다...

문제는 빈공간이 0, 종이구간 1인 배열을 만들지말고

그냥 순수하게 공간이 아닌 점으로 풀면 되는거였다. (면으로 풀면 답이나오긴 하던데...)

BFS와 DFS 둘다 사용해서 해결할 수 있다

DFS

#include<stdio.h>
#include<iostream>
#include<vector>
#include <algorithm>
 
using namespace std;
 
 
int m, n,sq; //m=5 ,n=7
int map[101][101];
int map2[101][101];
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };
bool check[101][101];
 
 
 
int go(int x, int y) {
 
    
    int cnt=1;
 
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
 
        if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
            if (check[nx][ny] == false && map[nx][ny] == 0) {
                check[nx][ny] = true;
                cnt += go(nx, ny);
                
            }
        }
    }
    
    return cnt;
 
}
 
int main() {
 
    //freopen("Text.txt", "r", stdin);
 
    cin >> m >> n >>sq; //m=5,n=7
 
    for (int i = 0; i < sq; i++) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
 
        for (int j = a; j <c; j++) {
            for (int k = b; k < d; k++) {
                map[j][k] = 1;
            }
        }
    }
 
    vector<int>ans;
    int area=0;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (map[i][j] == 0 && check[i][j] == false) {
                area++;
                check[i][j] = true;
                int answer = go(i, j);
                ans.push_back(answer);
            }
 
 
        }
 
    }
 
    cout << area << endl;
 
    sort(ans.begin(), ans.end());
 
    for (int i = 0; i < area; i++) {
        cout << ans[i] << " ";
    }
 
    return 0;
}
 
 
 
 

BFS

#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
 
using namespace std;
 
int n, m, sq;
int map[102][102];
int d[102][102];
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };
int sum = 0;
 
 
vector<int>ans;
queue<pair<int, int>>q;
 
 
void check(int a, int b) {
 
    int    cnt = 1;
 
    d[a][b] = cnt;
    q.push(make_pair(a, b));
 
    while (!q.empty()) {
        int x = q.front().first;
        int 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 && ny >= 0 && nx < n && ny < m) {
                if (map[nx][ny] == 0 && d[nx][ny] == 0) {
                    cnt++;
 
                    d[nx][ny] = cnt; // d에 방문 체크도 하면서 갯수도 입력
                    q.push(make_pair(nx, ny));
                }
            }
 
        }
 
    }
    ans.push_back(cnt);
    return;
}
 
 
int main() {
 
    //freopen("Text.txt", "r", stdin);
 
 
    cin >> n >> m >> sq;
 
    for (int i = 0; i < sq; i++) {
        int a, b;
        int c, d;
 
        cin >> a >> b >> c >> d;
 
 
        for (int j = a; j < c; j++) {
            for (int k = b; k < d; k++) {
 
                map[k][j] = 1;
 
            }
        }
    }
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (map[i][j] == 0 && d[i][j] == 0) {
                sum++;   // 빈 공간 갯수 세기
                check(i, j);
 
            }
        }
    }
 
    cout << sum << endl;
 
    sort(ans.begin(), ans.end());
    for (int i = 0; i < ans.size(); i++) {
        cout << ans[i] << " ";
    
    }
 
}