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

이런 문제는 

쉽게 짜면 쉽게 풀리지만

순서를 허투루 적었다간 나처럼 30분 날린다.

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

 

 

---

나의 첫번째풀이... (틀림) -> 전체를 검사하지 않음. (즉, 전체는 틀렸다고 가정하고 품)

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

using namespace std;

int N;
int sample[129][129];
int white = 0;
int blue = 0;

//N사각형 크기, a,b해당 사각형의 왼쪽 위 좌표
void func(int N, int a, int b) {

    if (N == 1) {
        if (sample[a][b] == 1) {
            blue++;
        }
        else {
            white++;
        }
        return;
    }
    //N크기의 사각형이면 4부분을 조사해야함
    //(a, b) (a, b+(N/2)) (a+(N/2), b) (a+(N/2), b+(N/2)) 4부분의 좌표를 조사해야함
    vector<pair<int, int>> vec;

    vec.push_back({ a,b });
    vec.push_back({ a, b + (N / 2) });
    vec.push_back({ a + (N / 2), b });
    vec.push_back({ a + (N / 2), b + (N / 2) });


    //비교를 위해 시작좌표의 값을 저장
    int check; // 기준
    int diff;  // 비교


    //4개의 시작좌표에 대해서 1/4크기의 사각형 4개 조사.    
    for (int k = 0; k < 4; k++) {
        auto cur = vec[k];
        check = sample[cur.X][cur.Y];
        diff = sample[cur.X][cur.Y];
        for (int i = 0; i < (N / 2); i++) {
            if (check != diff) break; // 2번 break
            for (int j = 0; j < (N / 2); j++) {
                //만약 다르면 그 사각형에 대해서 다시 조사해야함 -> 절반크기
                //해당 좌표에 대한 조사는 멈춤 (for문이 2개이기 때문에 2가지 break필요)
                if (check != sample[cur.X + i][cur.Y + j]) {
                    diff = sample[cur.X + i][cur.Y + j];
                    func(N / 2, cur.X, cur.Y);
                    break; // 1번 break
                }
            }
            
        }
        

        //만약 다르면 다음 사각형으로 넘어감.
        if (diff != check) {
            continue;
        }
        //만약 같으면그 사각형에 대해서는 모두 check을 가짐
        //해당 check 값을 가지는 색종이 숫자 ++
        if (check == 1){
            blue++;
        }
        else {
            white++;
        }
    }
   
    return;
}


int main() {
    cin >> N;
    //색종이 입력받음 인덱스 1번부터 사용
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> sample[i][j];
        }
    }
    func(N, 1, 1);

    cout << white << "\n" << blue;

}

 

이것도 테케가 맞게 나와서...ㅋㅋㅋㅋㅋㅋㅋㅋㅋ 엄청 헤메었다.

 

근데 여기에는 무슨 한계가 있었느냐???

전체를 검사하는 것을 까먹었다.

 

우선 다음 맞는 풀이를 보고

차이를 보고 설명해보겠다.

 

#맞는 풀이

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

using namespace std;

int N;
int sample[129][129];
int white = 0;
int blue = 0;

//N사각형 크기, a,b해당 사각형의 왼쪽 위 좌표 
// -> 전체를 조사하는 부분이 없네
void func(int N, int a, int b) {

    if (N == 1) {
        if (sample[a][b] == 1) {
            blue++;
        }
        else {
            white++;
        }
        return;
    }
    //N크기의 사각형이면 4부분을 조사해야함
    //(a, b) (a, b+(N/2)) (a+(N/2), b) (a+(N/2), b+(N/2)) 4부분의 좌표를 조사해야함
    vector<pair<int, int>> vec;
    vec.push_back({ a,b });
    vec.push_back({ a, b + (N / 2) });
    vec.push_back({ a + (N / 2), b });
    vec.push_back({ a + (N / 2), b + (N / 2) });


    //비교를 위해 시작좌표의 값을 저장
    int check; // 기준
    int diff;  // 비교

  
 
    
    check = sample[vec[0].X][vec[0].Y];
    diff = sample[vec[0].X][vec[0].Y];
    for (int i = 0; i < N; i++){
        if (check != diff) break; // 2번 break
        for (int j = 0; j < N; j++){
            //만약 다르면 그 사각형에 대해서 다시 조사해야함 -> 절반크기
            //해당 좌표에 대한 조사는 멈춤 (for문이 2개이기 때문에 2가지 break필요)
            if (check != sample[vec[0].X + i][vec[0].Y + j]) {
                diff = sample[vec[0].X + i][vec[0].Y + j];
                func(N/2, vec[0].X, vec[0].Y);
                func(N/2, vec[1].X, vec[1].Y);
                func(N/2, vec[2].X, vec[2].Y);
                func(N/2, vec[3].X, vec[3].Y);
                break; // 1번 break
            }
        }
            
    }

    //만약 다르면 해당 함수 종료
    if (diff != check) {
        return;
    }else{ // 같으면 색종이 추가
        if (check == 1) {
            blue++;
        }
        else{
            white++;
        }
        return;
    }

}


int main() {
    cin >> N;
    //색종이 입력받음 인덱스 1번부터 사용
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> sample[i][j];
        }
    }
    func(N, 1, 1);

    cout << white << "\n" << blue;

}

 

 

---

이러한 문제는

1. 전체를 검사한다.

1-1 전체에 문제가 없다.

1-2 결론

 

2. 전체 중에 문제가 있음

2-1 정사각형의 4개의 좌표를 뽑음

이 4개의 좌표를 이용해 다시 1로 돌아감

 

**2-2 정사각형의 4개의 좌표를 뽑을 수 없을 때 -> 즉, N이 1일 때 종료해야함 따로 예외 조건 달아놔야함.

 

위와 같은 순서를 가진다.

 

필수 조건은 전체를 검사하는 것, 그리고 4개의 좌표를 뽑을 수 없을 때 

이 2가지가 핵심이다.

 

전체를 검사하는 것이라 함은 -> 어떻게 검사하겠다라는 주된 방식을 의미하고

4개의 좌표를 뽑을 수 없을 때라 함은 -> 가장 최소 단위는 구별을 어떻게 할 것인가라는 것을 의미한다.

전체로 검사할 수 있음 하되.. 할 수 없으면 쪼개서 하겠다는 말이다.

 

재귀는 Divide & Conquer에 많이 쓰인다고 볼 수 있다.