백준 2630 색종이 만들기 / C++

문제 : 2630

풀이 point

분할정복과 재귀를 활용하면 된다.
어떻게 정사각형 안에 요소들이 모두 1이거나 0인지 판단할 것 인지(범위)
분할은 어떻게 진행될 것인지 생각해봐야한다.

우선 좌표를 받고 이중 for문을 통해 분할된 정사각형의 요소들이 모두 1이거나 0인지 판단하면 될 것 같다.
좌표는 4개로 분할되므로 총 사분면의 좌표를 주면 된다.
x, y
x, y+half
x+half, y
x+half, y+half
이 4개로 총 사분면의 좌표를 줄 수 있다.(사분면 첫 시작 좌표)
종료 조건은 정사각형의 요소들이 모두 1이거나 0일때 이다.

풀이 순서

정사각형의 요소들이 모두 1이거나 0인지 확인하는 함수
재귀 함수

코드

//백준 2630, 색종이 만들기

#include <iostream>

int N;
int grid[130][130];

int one{0}; int zero{0};

bool check(int n, int x, int y){
    int init = grid[x][y];
    for(int i{x}; i<x+n; ++i){
        for(int j{y}; j<y+n; ++j){
            if(grid[i][j] != init) return false;
        }
    }
    return true;
}

void recur(int n, int x, int y){
    if(check(n, x, y)){
        if(grid[x][y] == 1) ++one;
        else ++zero;
    }
    else{
        int half = n/2;
        recur(half, x, y);
        recur(half, x, y+half);
        recur(half, x+half, y);
        recur(half, x+half, y+half);
    }
}

int main(){
    std::cin >> N;
    for(int i{0}; i<N; ++i){
        for(int j{0}; j<N; ++j){
            std::cin >> grid[i][j];
        }
    }

    recur(N, 0, 0);
    std::cout << zero << '\n' << one;

    
    return 0;
}

사족

재귀를 풀기 위해 base condition도 생각해보고 분할 문제인거 같아 다양한 방법을 생각해봤는데 영 떠오르지 않았다.

좌표가 필요한거 같은데 어떻게 값을 줘야할까? 생각하면서 이전에 풀었던 Z문제를 떠올렸는데 조금만 유형이 달라지면 머리가 굳어버리는 메두사 머리라 그런지 Z처럼 풀면되는데 Z는 r-half, c-half라서 그냥 다르다고 생각해버렸다.

그래서 어? 좌표 없이도 괜찮을 거 같은데? 라는 생각을 해버리고... 이런 코드를 짜버렸다... 도저히 답이 안나온다고 생각해서 답지를 살짝 봤는데 하... 좌표가 맞았다. 애초에 좌표 없이도 괜찮을거라 생각한게 너무 바보 같은 사고방식이었다.

아무튼 for문 자체를 어떻게 돌릴까 고민했는데(사분면마다 시작과 끝이 달라지니깐) 이것도 쉽게 해결이 되는 부분이라 아 아직 실력이 한참 부족하구나 라는 것을 깨달은 계기... 그래도 이런류의 분할은 완전 정복하고 가는구나...

//백준 2630, 색종이 만들기

#include <iostream>

int N;
int grid[130][130];

int one{0}; int zero{0};
bool s1{false}; bool s2{false}; bool s3{false}; bool s4{false};
bool flag{false};
void recur(int n){

    if(n == 1){
        ++zero;
        return;
    }

    for(int i{0}; i<N; ++i){
        for(int j{0}; j<N; ++j){
            int init = grid[0][0];
            if(grid[i][j] != init){
                flag = false;
                break;
            }
            else flag = true;
        }
    }
    if(flag){
        if(grid[0][0] == 1) ++one;
        else ++ zero;
        flag = false;
        return;
    }
    
    int half = n/2;

    if(!s1){
        for(int i{0}; i<half; ++i){
            for(int j{0}; j<half; ++j){
                int init = grid[0][0];
                if(grid[i][j] == init) s1 = true;
                else{
                    s1 = false;
                    recur(n/2);
                }
            }
        }
        if(s1 && grid[0][0] == 1){
            ++one;
            std::cout << 'a';
        }
        else if(s1 && grid[0][0] == 0) ++zero;
    }

    //2
    if(!s2){
        for(int i{0}; i<half; ++i){
            for(int j{half}; j<N; ++j){
                int init = grid[0][half];
                if(grid[i][j] == init) s2 = true;
                else{
                    s2 = false;
                    recur(n/2);
                }
            }
        }

        if(s2 && grid[0][half] == 1){
            ++one;
            std::cout << 'b';
        }
        else if(s2 && grid[0][half] == 0) ++zero;
    }
    //3
    if(!s3){
        for(int i{half}; i<N; ++i){
            for(int j{0}; j<half; ++j){
                int init = grid[half][0];
                if(grid[i][j] == init) s3 = true;
                else{
                    s3 = false;
                    recur(n/2);
                }
            }
        }
    
        if(s3 && grid[half][0] == 1){
            ++one;
            std::cout << 'c';
        }
        else if(s3 && grid[half][0] == 0) ++zero;
    }
    //4
    if(!s4){
        for(int i{half}; i<N; ++i){
            for(int j{half}; j<N; ++j){
                int init = grid[half][half];
                if(grid[i][j] == init) s4 = true;
                else{
                    s4 = false;
                    recur(n/2);
                }
            }
        }

        if(s4 && grid[half][half] == 1){
            ++one;
            std::cout << 'd';
        }
        else if(s4 && grid[half][half] == 0) ++zero;
    }
}

int main(){
    std::cin >> N;
    for(int i{0}; i<N; ++i){
        for(int j{0}; j<N; ++j){
            std::cin >> grid[i][j];
        }
    }

    recur(N);
    std::cout << zero << '\n' << one;

    
    return 0;
}

이 코드 짜면서 하... 재귀가 이렇게 더러울리 없는데...ㅠㅠㅠㅠ 하면서 짰다.