[ C++/cpp ] 백준 (2630 색종이 만들이) ⭐재귀

BOJ 2630번 색종이 만들이

(실버 2)

 

문제링크 https://www.acmicpc.net/problem/2630

이렇게 4등분씩 쪼개서, 같은 색으로만 이루어진 정사각형의 개수를 카운팅하는 문제 !

 

 

(정답 코드)

#include <iostream>

using namespace std;

int n, white, blue;
int map[128][128];

bool isSameColor(int x, int y, int size, int color) {
    for(int i=x; i<x+size; i++) {
        for(int j=y; j<y+size; j++) {
            if(color == map[i][j]) continue;
            return false; // 중간에 다른 색 껴있음.
        }
    }
    return true;
}


void func(int x, int y, int size) {
    int color = map[x][y];
    
    if(isSameColor(x, y, size, color)) { // 모든 색이 같은 온전한 색종이가 완성됐다면,
        if(color) {
            blue++;
        } else {
            white++;
        }
        return; // 더이상 4등분 안 해도 됨. 종료 !
    }
    
    int new_size = size/2; // 4등분
    func(x, y, new_size);
    func(x+new_size, y, new_size);
    func(x, y+new_size, new_size);
    func(x+new_size, y+new_size, new_size);
}

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

    return 0;
}

 

 

📖 풀이 요약

 만약 아직 색종이가 완성되지 않았다면 또 4등분하고, 그래도 아직 색이 섞여있다면 또 4등분하고..

이런식으로 재귀로 풀어야하는 문제이다. 재귀의 틀만 생각해낸다면 구현하기는 크게 어렵진 않다. (이건 사실.. 모든 재귀 문제가 거의 그런 것 같다..ㅎ 틀 잡기가 쉽지 않지만 구현은 정말 3초컷인 !)

 

암튼 풀이는 간단하다. 현재 크기의 색종이에서 혹시 다른 색이 발견됐으면 ( isSameColor : False )

4등분이 더 필요하므로, new_size = size/2이런식으로 크기를 다시 반으로 쪼갠 후, 4분위를 다시 재귀 돌린다.

 

만약 현재 크기의 색종이에서 모든 색이 다 똑같으면 ( isSameColor : True )

이미 색종이 완성이니까 재귀는 종료하고, 각 색깔대로 카운팅 +1 해주면 된당 

 

 

 

---

 

사담사담

 

 요즘엔 주로 알고리즘 카테고리에 알고리즘 챕터별로 공부하고서 글을 올리는데, 시뮬레이션 챕터가 엄청 오래걸리기도 하고 이펍때문에 한 챕터 다잡고 문제풀고 공부해서 게시글 쓰기에 엄청 오래걸려서.. 지난 번에 공부했던 재귀 챕터 문제 복습할 겸 문제 풀어서 단독 게시물로 올려본당 ㅎㅅㅎ 중간고사 휴동 기간떄무네 너무 느슨하게 지냈는데.. 이제 다시 달려보쟛 아자자 ~!

 

참고로 지금은 새벽 2시고 나는 과방에 혼자이따...... 내일 아침 가게 오픈인디.. 언제 집가서 언제 씻징.. ㅋㅋㅋ쿠ㅜ 오랜만에 공부하려니까 집중력 진짜 3초라서 이펍 과제 찔끔하구 문제 딱 하나 풀었는데 새벽 2시 넘음 에바야 ~~!!~!~! 그리구 이 시간 공대 너무 깜깜하구 무셔워요 흑흑.. 얼른 집에갈랭