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

문제출처: https://www.acmicpc.net/problem/2630

2630번: 색종이 만들기

1. 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
 
using namespace std;
 
int paper[128][128];
int white = 0;
int blue = 0;
int N;
 
void count(int n, int x, int y) {
    int color = paper[x][y];
 
    for (int i = x; i < x + n; i++) {
        for (int j = y; j < y + n; j++) {
 
            //색이 다르면 4등분
            if (paper[i][j] != color) {
                count(n / 2, x, y); //nw
                count(n / 2, x + n / 2, y); //sw
                count(n / 2, x, y + n/2 ); //ne
                count(n / 2, x + n / 2, y + n/2); //se
                return;
 
            }
        }
    }
    if (color == 1)
        blue++;
    else
        white++;
}
 
int main() {
    scanf("%d", &N);//한 변의 길이
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%d", &paper[i][j]);
        }
    }
    count(N,0, 0);
 
    printf("%d\n%d", white, blue);
}

 

2. 해결과정

color 변수에 현재 색종이의 색을 할당해주고, 이중 for문을 이용하여 color와 다른 색상이 현재 사분면에 존재하는지 확인한다. color와 다른 색상이 존재하면 현재 사분면을 4등분하여 각각 나눠진 사분면을 재귀로 호출 -> 호출값을 return

(nw= 왼쪽 위, sw= 왼쪽 아래, ne =오른쪽 위, se=오른쪽 아래)

현재 사분면이 모두 같은 색이면 color 색상에 따라 white, blue 변수에 카운트 해주면 된다.

 

3. 느낀점

재귀를 사용하면 확실히 코드가 간결해진다. 재귀를 몰아서 왁 푸니까 재귀로 풀수 있었는데 과연 따로 존재하는 문제였다면 내가 재귀를 생각할 수 있었을까? 고민해봐야할듯,,, 공부하자!!