[BOJ, C++]#2630_색종이 만들기, 분할-정복, divide-and-conquer, 재귀 호출

#1. 문제

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

 

---

 

#2. 풀이

 

1. 분할-정복 알고리즘

[알고리즘]#4_분할-정복 알고리즘

분할-정복 알고리즘은 하나의 문제를 여러 하위 부분 문제들로 분할하여, 재귀적으로 이를 해결하고 그 결과 값들을 병합하여 최적해를 찾아내는 최적화 기법 중 하나입니다.

 

2. 4개로 분할, 그리고 재귀 호출

1. 먼저, 병합(탐색 종료) 조건을 설정합니다. 종료 조건은 색종이 크기가 1이 되거나, 현재 크기의 색종이 칸들이 모두 같은 색일 경우에 종료되도록 설정합니다. 종료 조건을 만족하면, 색종이 색을 찾아서 해당 색의 카운트를 +1 해줍니다.
2. 다음으로, 분할 작업을 설정합니다. 현재 크기의 색종이를 n/2 x n/2 크기로 총 4개로 분할하며, 이들에 대하여 재귀 호출을 수행합니다.

 

---

 

#3. 코드

/*
    @링크: https://www.acmicpc.net/problem/2630
*   @문제: 색종이 만들기
*   @설명
        1. 분할-정복, 재귀 DFS
*/


#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair<int,int> p;

int N;
vector<vector<int>> paper;
vector<int> res;

bool checkIsSame(const p& start, const int& size)
{
    int startY = start.first;
    int startX = start.second;
    int color = paper[startY][startX];

    for(int i=startY; i<startY+size; ++i)
    {
        for(int j=startX; j<startX+size; ++j)
        {
            if(paper[i][j] != color)
            {
                return false;
            }
        }
    }

    return true;
}

void dfs(const p& start, int size)
{
    int cy = start.first;
    int cx = start.second;

    if(size == 1)
    {
        res[paper[cy][cx]]++;
        return;
    }
    if(checkIsSame(start, size))
    {
        res[paper[cy][cx]]++;
        return;
    }

    int half = size / 2;
    dfs({cy, cx}, half);
    dfs({cy, cx + half}, half);
    dfs({cy + half, cx}, half);
    dfs({cy + half, cx + half}, half);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N;

    paper.resize(N, vector<int>(N));

    for(int i=0; i<N; ++i)
    {
        for(int j=0; j<N; ++j)
        {
            cin >> paper[i][j];
        }
    }

    // 결과 벡터 초기화 변경
    res = vector<int>(2, 0);

    dfs({0,0}, N);  // paper.size() 대신 N 사용

    cout << res[0] << '\n' << res[1];

    return 0;
}

 

---