2630번 - 색종이 만들기 (C++)

[문제]

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

---

[해결 방법]

 

 우선 void check(int x, int y, int N) 함수를 정의하여, 재귀 함수를 통해 풀려고 하였다.

(x, y는 판 내 좌표, N은 전체 종이의 크기)

 

첫번째로,

일단 (0,0) 좌표와 사용자에게 입력받은 N(그림에서는 8)을 check 함수에 인자로 전달하였다.

그리고 for문을 통해서 check(x,y,N/2)를 통해 (그림 내에서) 8 X 8 -> 4 X 4 -> 2 X 2 -> 1 X 1 이런식으로 분할하려고 하였다.

 

bool test(int x, int y, int N) 은 주어진 좌표에서 (x,y) ~(가로 + N, 세로 + N) 만큼 범위에서 같은 수 인지 아닌지 파악하는 함수이다.

만약 주어진 x,y 좌표와 i, j 좌표가 다르면 false를 리턴하고, 같다면 true를 리턴하도록 하여 구분하도록 하였다.

 

재귀함수에서는 Base Condition이 필요한데, Base Condition이란 종료 조건을 의미한다.

종료 조건으로 N 범위내에서 모두 같은 수인 경우 -> (파란색 칸 + 1 or 하얀색 칸 + 1)을 하도록 하고,

파란색 칸이 모두 같은 경우 -> blue++, 하얀색 칸이 모두 같은 경우 -> white++

return 을 통해 그만 탐색하도록 하였음.

 

그리고 재귀적으로 위의 그림에서 (0,0)에서 N/2 를 다 탐색했을 경우 -> for문에서 i+N/2, j+N/2를 check에 추가하여 분할 탐색하도록 하였다.

 

---

 

[정답 코드]

#include <bits/stdc++.h>

int arr[130][130];
int white = 0;
int blue = 0;

using namespace std; 

bool test(int x, int y, int N)
{
    for(int i=x; i<x+N; i++)
    {
        for(int j=y; j<y+N; j++)
        {
            if(arr[x][y] != arr[i][j])
                return false;
        }
    }
    return true;
}

void check(int x, int y, int N)
{
    if(test(x,y,N) == true) // test condition
    {
        if(arr[x][y] == 1)
            blue++;
        else if(arr[x][y] == 0)
            white++;

        return;
    }
    for(int i=x; i<x+N; i+=N/2)
    {
        for(int j=y; j<y+N; j+=N/2)
        {
            check(i,j,N/2);
        }
    }
}

int main()
{
    
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int N;
    cin >> N;
    
    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++)
            cin >> arr[i][j];
            
    check(0, 0, N);
    cout << white << "\n" << blue;
}