[BaekJoon/백준] 2630번 분할정복

 

분할정복단원 첫 시작

 

프로그램의 흐름은 이런식으로 구성하게 된다.

 

각 재귀함수에서, 위치를 다룰 때

"시작x, 시작y, 끝x, 끝y" 이런식으로 입력받을 수도 있겠으나,

네 군데이다 보니 코딩함에 있어서 다소 어지러워 보일 수 있다.

 

그래서 그림의 왼쪽 위의 그림을 참고해서 생각해보면 조금 더 간단하게 다뤄줄 수 있다.

"시작 x, 시작 y, 사각형의 크기" 이런식으로 말이다. 이런방식을 채택하도록 노력해야한다.

#include <stdio.h>
int arr[128][128];
int N;

int one;
int zero;

// 시작점과 사각형 크기
void divide_conquer(int x, int y, int n) {
    
    int sum = 0;
    
    for(int i = x; i < x + n; i++)
        for(int j = y; j < y + n; j++)
            sum += arr[i][j];
    
    if(sum == n*n) { // 모두 1
        one++;
    } else if(sum == 0) { // 모두 0
        zero++;
    } else { // 나눠줘야함.
        
        divide_conquer(x, y, n/2); // 왼쪽 위
        divide_conquer(x, y + n/2, n/2); // 오른쪽 위
        divide_conquer(x + n/2, y, n/2); // 왼쪽 아래
        divide_conquer(x + n/2, y + n/2, n/2); // 오른쪽 아래
        
    }
    
}

int main() {
    scanf("%d", &N);
    
    for(int i = 0; i < N; i++) {
        for(int j= 0; j < N; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
    divide_conquer(0, 0, N);
    
    printf("%d %d", zero, one);
}

내 코드 같은 경우는

divide_conquer 함수 내에서, 모두 1 또는 0으로 채워졌는지를 확인하는 데 있어서 전체 배열을 모두 돌아서 다소 비효율적일 수 있다.

이걸, 맨 처음 기본값 세팅해준 뒤 하나라도 다른 게 나오면 바로 나눠주는 작업을 수행하여 굳이 배열 전체를 돌게 할 필요가 없게 할 수도 있겠다.

 

 

이에 대해 참고하실 분은 이 분의 코드가 잘 정리되어 있어서 참고하면 좋겠다.

stillchobo.tistory.com/72

#include <iostream>
#include <stdio.h>

using namespace std;

int n;
int arr[129][129];
int w;
int b;

void check(int size, int startX, int startY)
{
    int target = arr[startX][startY];
    
    for(int x = startX; x < startX + size; x++)
    {
        for(int y = startY; y < startY + size; y++)
        {
            if(arr[x][y] != target)
            {
                check(size/2, startX, startY);
                check(size/2, startX + size/2, startY);
                check(size/2, startX, startY + size/2);
                check(size/2, startX + size/2, startY + size/2);
                
                return;
            }
        }
    }
    
    if(target == 0) w++;
    else b++;
}

int main()
{
    cin >> n;
    
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n ; j++)
        {
            cin >> arr[i][j];
        }
    }
    
    check(n, 0, 0);
    
    cout << w << "\n" << b;
}