[Algorithm] 백준 - 색종이 만들기 (2630번)

문제

[백준] 색종이 만들기
(Olympiad > 한국정보올림피아드 > KOI 2001 > 중등부)

사용 알고리즘

- 분할 정복

- 재귀

해결방법

• 종이를 한 변의 길이가 절반이 되게끔 자른다고 생각하고 문제를 해결한다
• 종이를 자르는 경우는 기준위치의 색깔과 현재 위치의 색깔이 다를 때 종이를 자른다
• 한 변의 길이가 절반이 되게 자르는 경우, 종이 4장이 생성되는데, 이 때 각 종이의 기준위치는 다음과 같다
  • 길이 : N 일때, 기준위치 (col, row) // (0, 0)이다
    • 종이1 > 길이 : N/2, 기준위치 (col, row)
    • 종이2 > 길이 : N/2, 기준위치 (col, row+N/2)
    • 종이3 > 길이 : N/2, 기준위치 (col+N/2, row)
    • 종이4 > 길이 : N/2, 기준위치 (col+N/2, row+N/2)
• 각 정사각형을 탐색하면서, 모두 같은 색깔로 이루어진 경우 res[color]를 증가시키고, 모두 같은 색이 아닌 경우 한 변의 길이가 절반이 되게 또 자른다. (한 변의 길이가 1일 때 까지 계속 반복 => 재귀함수 탈출조건)

예제 1

1. 한 변의 길이 : 8 / 기준위치 (0, 0) / 색깔 : 1 (파란색)
   
   1. 탐색 순서
      (0,0) > (0,1) > (0,2)
   2. 재귀함수 호출
      (0,2) 에서 색깔이 다르므로, 한 변의 길이 절반이 되도록 종이 절단
      1. (0, 0)에서 길이가 4인 종이 탐색
      2. (0, 4)에서 길이가 4인 종이 탐색
      3. (4, 0)에서 길이가 4인 종이 탐색
      4. (4, 4)에서 길이가 4인 종이 탐색
2. 한 변의 길이 : 4 / 기준위치 (0, 0) / 색깔 : 1 (파란색)
   1. 탐색순서
      (0,0) > (0,1) > (0,2)
   2. 재귀함수 호출
      (0,2) 에서 색깔이 다르므로, 한 변의 길이 절반이 되도록 종이 절단
      
      1. (0,0)에서 길이가 2인 종이 탐색
      2. (0,2)에서 길이가 2인 종이 탐색
      3. (2,0)에서 길이가 2인 종이 탐색
      4. (2,2)에서 길이가 2인 종이 탐색
3. 한 변의 길이 : 2 / 기준위치 (0, 0) / 색깔 : 1 (파란색)
   1. 탐색순서
      (0,0) > (0,1) > (1,0) > (1,1)
   2. is_square = true 이므로, res[color] 값 증가
4. 한 변의 길이 : 2 / 기준위치 (0,2) / 색깔 : 0 (하얀색)
   1. 탐색순서
      (0,2) > (0,3) > (1,2) > (1,3)
   2. is_squre = true 이므로, res[color] 값 증가
5. 생략
6. 생략

소스코드

사용언어 : C++

#include <iostream>

using namespace std;

int N;
int paper[130][130];
int res[2];

void check_paper(int col, int row, int line) 
{
    if (col >= N || row >= N || line < 1) return;

    int color = paper[col][row];
    bool is_square = true;

    for (int i=col; i<col+line; i++) {
        if (!is_square) break;
        for (int j=row; j<row+line; j++) {
            if (paper[i][j] != color) { // 기준위치 컬러와 다른 경우, 종이 절단
                check_paper(col, row, line/2);
                check_paper(col, row+line/2, line/2);
                check_paper(col+line/2, row, line/2);
                check_paper(col+line/2, row+line/2, line/2);
                is_square = false;
                break;
            }
        }
    }
    
    // 길이가 line인 정사각형이 모두 같은 색으로 이루어졌을 때
    if (is_square) res[color]++;
}

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

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

    check_paper(0, 0, N);

    cout << res[0] << "\n" << res[1];
    
    return 0;
}

 

한줄평

처음엔 종이의 한 변의 길이가 절반이 되게 절단 했을 때, 생성되는 4장의 종이의 기준위치 좌표를 어떤식으로 찾아야 할지 감이 안와서 많이 헤맸다. 고생해서 구한 좌표 구하는 함수도 첨가

#define cp pair<int, int> // (column, row)

// 기준위치 좌표 찾는 함수
vector<cp> find_coordinates(int col, int row, int step)
{
    vector<cp> coordis;

    int ncol = col;
    for (int i=0; i<2; i++) {
        int nrow = row;
        for (int j=0; j<2; j++) {
            if (nrow >= N || ncol >= N) continue;
            coordis.push_back(make_pair(ncol, nrow));
            nrow += step;
        }
        ncol += step;
    }
    return coordis;
}

void check_paper(int col, int row, int line)
{
    // 절단 후 생성된 종이들의 기준위치 좌표
    vector<cp> coordis = find_coordinates(col, row, line);
    
    for (const auto& c : coordis) {
        int col = c.first;
        int row = c.second;
        int color = paper[col][row];

        bool is_square = true;
        for (int i=col; i<col+line; i++) {
            if (!is_square) break;
            for (int j=row; j<row+line; j++) {
                if (i >= N || j >= N) break;
                
                // 시작점과 컬러가 다른 경우 => 종이 N/2으로 쪼개기
                if (paper[i][j] != color) {
                    is_square = false;
                    check_paper(col, row, line/2);
                    break;
                }
            }
        }
        if (is_square) {
            res[color]++;
        }
    }
}