[알고리즘] 2583번: 영역 구하기

0. 문제

 

2583번: 영역 구하기

 

---

1. 문제 이해

 

1. 100 * 100 배열을 그린다.
2. K개의 직사각형을 그린다.
3. for(첫번째 꼭짓점의 y ~ 두 번째 꼭짓점의 y) 안에 for(첫 번째 꼭짓점의 x ~ 두 번째 꼭짓점의 x) 이중 for문을 사용한다.
4. 각각의 연결된 컴포넌트들의 넓이를 구해서 저장한다.
5. dfs로 연결된 컴포넌트의 수를 센다.

 

---

2. 제출

 

가. 실패

// 백준 2583: 영역 구하기
#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

const int mn = 100;
int m, n, k, ret=0, area, a[mn][mn], visited[mn][mn];
int dy[] = {-1,0,1,0};
int dx[] = {0,1,0,-1};
vector<int> v;

void dfs(int y, int x){
    visited[y][x] = 1;
    area++;
    for(int i=0; i<4; i++){
        int ny = y + dy[i];
        int nx = x + dx[i];
        bool underflow = ny < 0 || nx < 0;
        bool overflow = m <= ny || n <= nx;
        if(underflow || overflow) continue;
        if(a[ny][nx] == 1 && !visited[ny][nx])
            dfs(ny, nx);
    }
    return;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    memset(a, 1, sizeof(a));
    memset(visited, 0, sizeof(visited));

    cin >> m >> n >> k;
    for(int i=0; i<k; i++){
        int x1,x2,y1,y2;
        cin >> x1 >> y1 >> x2 >> y2;
        for(int y=y1; y<y2; y++){
            for(int x=x1; x<x2; x++){
                a[y][x] = 0;
            }
        }
    }

    for(int y=0; y<m; y++){
        for(int x=0; x<n; x++){
            if(a[y][x]==1 && !visited[y][x]){
                area = 0;
                ret++;
                dfs(y,x);
                v.push_back(area);
            }
        }
    }

    cout << ret << "\n";
    for(int i : v) cout << i << " ";
    cout << "\n";

    return 0;
}

• memset은 0, -1, char 한 글자로만 초기화 가능함. 그래서 1로 초기화할려면 memset 대신에 fill을 사용해야함. 그냥 처음부터 fill 쓰는 것이 정신건강에 더 이로울 것 같다.

 

---

나. 수정

// 백준 2583: 영역 구하기
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int mn = 100;
int m, n, k, ret=0, area, a[mn][mn], visited[mn][mn];
int dy[] = {-1,0,1,0};
int dx[] = {0,1,0,-1};
vector<int> v;

void dfs(int y, int x){
    visited[y][x] = 1;
    area++;
    for(int i=0; i<4; i++){
        int ny = y + dy[i];
        int nx = x + dx[i];
        bool underflow = ny < 0 || nx < 0;
        bool overflow = m <= ny || n <= nx;
        if(underflow || overflow) continue;
        if(a[ny][nx] == 1 && !visited[ny][nx])
            dfs(ny, nx);
    }
    return;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    fill(&a[0][0], &a[0][0] + mn*mn, 1);
    fill(&visited[0][0], &visited[0][0] + mn*mn, 0);

    cin >> m >> n >> k;
    for(int i=0; i<k; i++){
        int x1,x2,y1,y2;
        cin >> x1 >> y1 >> x2 >> y2;
        for(int y=y1; y<y2; y++)
            for(int x=x1; x<x2; x++)
                a[y][x] = 0;
    }

    for(int y=0; y<m; y++){
        for(int x=0; x<n; x++){
            if(a[y][x]==1 && !visited[y][x]){
                area = 0;
                ret++;
                dfs(y,x);
                v.push_back(area);
            }
        }
    }
    cout << ret << "\n";
    sort(v.begin(), v.end());
    for(int i : v) cout << i << " ";
    cout << "\n";

    return 0;
}

• area를 통해서 넓이를 구함.
• fill(&a[0][0], &a[0][0] + mn*mn, 1); : 배열 a를 1로 초1기화.
• sort(v.begin(), v.end()); : vector 오름차순 정렬

 

    cin >> m >> n >> k;
    for(int i=0; i<k; i++){
        int x1,x2,y1,y2;
        cin >> x1 >> y1 >> x2 >> y2;
        for(int y=y1; y<y2; y++)
            for(int x=x1; x<x2; x++)
                a[y][x] = 0;
    }

꼭짓점을 바탕으로 직사각형을 그려서 해당 영역에 0을 대입.

 

 

다. 참고

vector<int> ret;

int dfs(int y, int x)_
	visited[y][x] = 1;
	int area = 1;
	for(int i=0; i<4; i++){
		int ny = y + dy[i];
		int nx = x + dx[i];
		bool underflow = ny < 0 || nx < 0;
		bool overflow = m <= ny || n <= nx;
		if(underflow || overflow) continue;
		if(a[ny][nx] == 1 && !visited[ny][nx])
			area += dfs(ny, nx);
	}
	return area;
}

...
int main(){

	...

	for(int y=0; y<m; y++){
		for(int x=0; x<n; x++){
			if(a[y][x]==1 && !visited[y][x]){
				ret.push_back(dfs(y,x));
			}
		}
	}

	sort(v.begin(), v.end());
	cout << ret.size() << "\\n";
	for(int i : ret) cout << i << " ";
	cout << "\\n";

	return 0;
}

• area += dfs(ny, nx);, return area : 전역변수 area를 사용하지 않고 dfs가 area를 반환하도록 작성할 수 있음.
• cout << ret.size() << "\n";, for(int i : ret) cout << i << " "; : 개수와 넓이를 하나의 벡터로 해결.