백준, BOJ, 1780번 C++ [CPP]

이것 또한

분할 정복

Z자로 진행하는 방식이다.

더 어려워졌다면 9개로 늘어난거..?

시간도 많다

 

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

 

---

 

#맞은 풀이

틀린 부분에 대해서는 내가 주석을 좀 달아놨다.

#include<iostream>
#include<vector>
#define X first
#define Y second

using namespace std;

int N;
int map[2200][2200];

int mm = 0;
int zz = 0;
int pp = 0;

void func(int N, int a, int b) {
    if (N == 1) {
        int std = map[a][b];
        if (std == 1) {
            pp++;
        }
        else if (std == 0) {
            zz++;
        }
        else {
            mm++;
        }

        return; // N=1이면 여기까지만 진행
    }

    //9개의 좌표
    vector<pair<int, int>> vec;
    vec.push_back({ a,b });
    vec.push_back({ a,b + N/3 });
    vec.push_back({ a,b + 2*N/3 });
    vec.push_back({ a + N / 3,b });
    vec.push_back({ a + N / 3,b + N / 3 });
    vec.push_back({ a + N / 3,b + 2 * N / 3 });
    vec.push_back({ a + 2 * N / 3,b });
    vec.push_back({ a + 2 * N / 3,b + N / 3 });
    vec.push_back({ a + 2 * N / 3,b + 2 * N / 3 });


    int check = map[a][b]; // 기준
    int diff = map[a][b]; // 비교


    //전체를 체크해서 아니면 9개로 가름
    //0부터 시작해야함...또틀림
    for (int i = 0; i<N; i++) {
        if (check != diff)break; //2
        for (int j = 0; j<N; j++) {
            //만약 이 종이에 다른 것이 섞여있다면
            //이 for문은 소용없음 2중 루프이므로 break포인트 2개
            //9개로 나눔.
            if (check != map[a+i][b+j]) {
                diff = map[a+i][b+j];
                func(N / 3, vec[0].X, vec[0].Y);
                func(N / 3, vec[1].X, vec[1].Y);
                func(N / 3, vec[2].X, vec[2].Y);
                func(N / 3, vec[3].X, vec[3].Y);
                func(N / 3, vec[4].X, vec[4].Y);
                func(N / 3, vec[5].X, vec[5].Y);
                func(N / 3, vec[6].X, vec[6].Y);
                func(N / 3, vec[7].X, vec[7].Y);
                func(N / 3, vec[8].X, vec[8].Y);
                break; // 1
            }
        }
    }
    //다르면 종료
    if (diff != check) {
        return;
    }
    // 끝까지 같으면
    else {
        if (check == diff) {
            if (check == 1) {
                pp++;
            }
            else if (check == 0) {
                zz++;
            }
            else {
                mm++;
            }
        }
    }

    
}

int main() {
    cin >> N;
    //N*N개 입력, 인덱스 1부터 씀.
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> map[i][j];
        }
    }

    func(N, 1, 1);

    cout << mm << "\n" << zz << '\n' << pp;


}

 

여기서 포인트는

 

전체를 먼저 검사하고 그것이 안되면

9가지로 나눈다는 것.(좌표넣을 순서는 어떤 식인지 관찰해서 얻어내자) -> 여기선 상관없었음

가장 작게 나눴을 때 종료조건을 만들어줘야 한다는 것.

 

이와 비슷한 문제가 또 있다.

[문제풀이(Problem Solving)] - 백준, BOJ, 1992번 C++ [CPP]

[문제풀이(Problem Solving)] - 백준, BOJ, 2630번 C++ [CPP]