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

이것 또한

분할 정복

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

더 어려워진다면 Z자가 아니라 새롭게 진행하는 방식이겠지

시간도 많다

 

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

 

---

 

#맞은 풀이

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

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


using namespace std;

int N;
int pic[65][65];

//N의 크기를 가지고 왼쪽 위 좌표가 a,b인 정사각형
void func(int N, int a, int b) {

    //가장 잘게 쪼갰을 때
    if (N == 1) {
        //구현
        //해당 값 출력
        cout << pic[a][b];

        //종료
        return;
    }

    //4군데 좌표를 얻어야함
    //(a,b) , (a,b+N/2), (a+N/2,b), (a+N/2, b+N/2)
    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 = pic[a][b]; // 모두다 같은지 기준
    int diff = pic[a][b]; // 모두다 같은지 비교

    //전체를 뒤져서 아니면 4개로 나눔 
    // 이번 인덱스는 0부터 시작해야함...이거 틀림
    for (int i = 0; i <N; i++){
        if (check != diff) break; // 2
        for (int j = 0; j <N; j++) { // 0부터시작
            //전체가 다 같지 않으면 4개로 나눔.
            //전체가 다 같지 않으면 for문을 더 돌릴 필요 없음 break포인트 2개
            if (pic[vec[0].X +i][vec[0].Y + j] != check){
                diff = pic[vec[0].X + i][vec[0].Y + j];
                cout << "(";
                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);
                cout << ")";
                break; // 1
            }
        }
        
    }
    //만약 다 같으면 -> 해당숫자 출력
    if (check == diff) {
        cout << check;
    }
}

int main() {
    cin >> N;
    //공백없이 입력받을 때 , index는 1부터사용, N번 입력받음
    for (int i = 1; i <=N; i++) {
        string s = "";
        cin >> s;
        int seq = 1;
        //char이므로 int로 바꿔서 넣어줘야함 **이것때문에 틀림!!
        for (char c : s) {
            int x = c - '0';
            pic[i][seq++] = x;
        }
    }
    func(N, 1, 1);
}

 

여기서 포인트는

 

입력조차도 공백 없이 주어졌다는 것

-char를 int로 바꾸기 위해 -'0' 연산하여 아스키코드 값을 썼다는 것

 

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

4가지로 나눈다는 것.(좌표넣을 순서는 어떤 식인지 관찰해서 얻어내자)

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

 

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

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