[C언어] 2630번 색종이 만들기 - 분할 정복, 재귀

#include <stdio.h>

int arr[129][129];
int N, w, b;

int DQ(int n, int x, int y)  //몇 번 나눠졌는가, 가장 왼쪽 위 종이의 위치가 어디인가?
{
    int i, j;
    int k=N, flag=0;
    
    for(i=0; i<n; i++)
        k/=2;
    
    for(i=0; i<k; i++) {
        for(j=0; j<k; j++) {
            if(arr[x+i][y+j] != arr[x][y]) {
                flag=1;
                break;
            }
        }
        if(flag)
            break;
    }
    if(flag && k!=1) {  //4가지로 나누기
        DQ(n+1, x, y);
        DQ(n+1, x+k/2, y);
        DQ(n+1, x, y+k/2);
        DQ(n+1, x+k/2, y+k/2);
    }
    else {  //단색으로 이루어져있는 경우
        if(arr[x][y])  //파란색일 경우
            b++;
        else
            w++;
    }
}

int main()
{
    int i, j;
    
    scanf("%d", &N);
    
    for(i=1; i<=N; i++)
        for(j=1; j<=N; j++)
            scanf("%d", &arr[i][j]);

    DQ(0, 1, 1);
    
    printf("%d\n%d", w, b);
    
    return 0;
}

 

2로 나눈 것을 보고 바로 분할정복을 써야되겠다고 생각하였다. 재귀로 푸는게 맞을 것 같고 정사각형의 크기와 제일 왼쪽 위 좌표를 넘겨주는 것으로 풀 수 있을 거라고 생각하였다. 정사각형의 크기는 몇 번으로 나누는지로 했고 4개로 나눠서 파란색은 1을, 흰색은 0을 반환하는 것으로 풀었다. 

 

재귀로 풀고 나서 다른 사람의 코드를 보고 나서 반 코드가 필요 없길레 조금 고쳤다

 

#include <stdio.h>

int main(){
int n,m,i,j,cnt=-1,a[10000],b[10000],com[101]={0, 1};

scanf("%d%d",&n,&m);
for(i=1; i<=m; i++)
scanf("%d%d",&a[i],&b[i]);
for(i=1; i<=n;i++){
for(j=1;j<=m; j++){
if(com[a[j]]==1)
com[b[j]]=1;
if(com[b[j]]==1)
com[a[j]]=1;
}
}
for(i=0; i<=n; i++){
if(com[i]==1)
cnt++;
}
printf("%d\n",cnt);
}

 

되게 간단하게 풀러버렸다.

 

 

 

 

※현재 고등학교 등교중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.