백준 2630 - 색종이 만들기

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

2630번: 색종이 만들기

분할 정복을 연습하기 위한 첫 번째 문제

쿼드트리는 분할이 4개씩 되는 알고리즘을 의미하는 듯 싶다

 

알고리즘

slice_blue (int row_start, int row_end, int col_start, int col_end, int res)

//해당 구간에서의 파란색 종이의 수를 구하는 함수

 

//base condition

if(길이 = 1)

  return 해당 타일의 색 //파랑 = 1

 

int firstColor = paper[row_start][col_start] //시작 위치의 종이 색깔을 기억

for(i=row_start, i<row_end;i++)

    for(j=col_start, j<col_end;j++) {

        if(paper[i][j]!=firstColor) //색깔이 한번이라도 다르면

            break;

 

if(색깔이 다른 경우)

//divide

    int row_mid = (row_start + row_end) / 2, int col_mid = (col_start + col_end) / 2; //구간 분할을 위해 중간 위치 저장

    piece += 3 // 한번 분할이 일어날 때마다 전체 조각의 수가 3개씩 추가됨

    res+= slice_blue(1번 구간);

    res+= slice_blue(2번 구간);

    res+= slice_blue(3번 구간);

    res+= slice_blue(4번 구간);

else(모든 구간이 색 동일)

    res += firstColor;

 

return res;

 

main()

    int blue = slice_blue(0, n, 0, n, 0);

    int white = piece - blue; //종이 조각은 흰색이거나 파란색이므로, 두 종이의 수를 합치면 전체 색종이 조각 수와 같다.

 

 

 

각 구간의 정의 (r : row, c : column, s : start, m : mid, e : end)

1 r_s~r_m c_s~c_m	2 r_s~r_m c_m~c_e
3 r_m~r_e c_s~c_m	4 r_m~r_e c_m~c_e

 

 

시간복잡도 : nlogn

(n은 정사각형의 크기)

 

한번 분할할 때마다 크기는 4분의 1, 수행할 함수는 4개가 되며 분할 전에 정사각형 전체를 탐색하므로

f(n) = 4*f(n/4) + n + c

n=4k라 하면 f(4k) = 4*f(4k-1) + 4k,

f(4k) = ak라 하면 ak+1 = 4ak + 4k, 점화식 공식 이용하면 ak = 4k + k4k, k=log4n이므로

ak = f(n) = n+nlogn = O(nlogn)

 

*느낀점

재귀함수는 구현이 까다롭지만 개념 자체는 그렇게 복잡하지 않아서 분할 방식과 base condition만 제대로 설정하면 될 거 같다. 하얀 종이를 분할정복 없이 계산한 건 잘한듯