[C/C++] #2583 영역 구하기(깊이 우선 탐색)

이번 문제는 복합 문제입니다.

 

calculate area

 

색종이 붙이기 문제와, 섬의 갯수 구하기 문제가 결합된 문제라고 생각하시면 편합니다.

 

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

2583번: 영역 구하기

 

색종이 붙이기 문제는 캔버스를 생성한다음, 색칠하기만을 하시면 됩니다.  \(O(MNK)\) 알고리즘이긴 하지만, 조금 더 개선을 하시면, \(O(MN+K)\) 알고리즘으로도 하실 수 있습니다.

 

https://sdev.tistory.com/1547

[C/C++] 백준 #2567 색종이-2(구현)

 

섬 갯수 구하기 문제는 깊이 우선탐색을 이용하면 간단하게 해결할 수 있습니다.  방문 배열을 따로 잡지 않고, map자체에 적용하시면 더 간단하게 구현하실 수 있습니다.

 

https://sdev.tistory.com/870

[C/C++] 백준 #1743 음식물 피하기(너비우선탐색)

 

섬의 개수 구하는 것은 깊이 우선 탐색을 하셔도 괜찮고 너비 우선 탐색을 하셔도 괜찮습니다.  편하신 알고리즘을 선택해서 구현하시면 됩니다.  제 경우에는 깊이 우선 탐색을 이용해서 풀었습니다.

 

//----------------------------------------------------
//    baekjoon #2583
//        - by Aubrey Choi
//        - created at 2019-09-08
//----------------------------------------------------
#include <stdio.h>
#include <algorithm>

char canvas[100][100];
void draw(int a, int b, int c, int d)
{
    for(int i=b;i<d;i++) for(int j=a;j<c;j++) canvas[i][j]=1;
}
int dfs(int r, int c, int h, int w)
{
    int ret=1;
    canvas[r][c]=2;
    if(r<h-1&&canvas[r+1][c]==0) ret+=dfs(r+1,c,h,w);
    if(c<w-1&&canvas[r][c+1]==0) ret+=dfs(r,c+1,h,w);
    if(r>0&&canvas[r-1][c]==0) ret+=dfs(r-1,c,h,w);
    if(c>0&&canvas[r][c-1]==0) ret+=dfs(r,c-1,h,w);
    return ret;
}
int main()
{
    int m, n, k, a, b, c, d, v[5000], p=0;
    scanf("%d%d%d",&m,&n,&k);
    while(k--) { scanf("%d%d%d%d",&a,&b,&c,&d); draw(a,b,c,d); }
    for(int i=0;i<m;i++) for(int j=0;j<n;j++) if(canvas[i][j]==0) v[p++] = dfs(i, j, m, n);
    std::sort(v,v+p);
    printf("%d\n",p);
    for(int i=0;i<p;i++) printf("%d ", v[i]); putchar('\n');
    return 0;
}