백준 C# - 2630 +) 풀이

분할 정복 문제이다.

예제를 보면서 어떻게 분할할지 생각해보자

8
1 1 0 0 0 0 1 1
1 1 0 0 0 0 1 1
0 0 0 0 1 1 0 0
0 0 0 0 1 1 0 0
1 0 0 0 1 1 1 1
0 1 0 0 1 1 1 1
0 0 1 1 1 1 1 1
0 0 1 1 1 1 1 1

알고리즘 생각

부분 색종이는 모두 같은 색상이어야한다. 그렇지 않는 경우 색종이를 1/2씩 분할하여 모두 같은 색인지 다시 체크하며 재귀적으로 확인한다.

위의 생각을 코드로 표현해보자

01 부분 색종이가 모두 같은 색상인지 체크

int firstColor = paper[row, col];

bool isSame= true;
for (int i = row; i < row + size; i++)
{
    for (int j = col; j < col + size; j++)
    {
        if (paper[i, j] != firstColor)
        {
            isSame = false;
            break;
        }
    }
    if (!isSame)
        break;
}

if (isSame)
{
    if (firstColor == 0)
        whiteCount++;
    else
        blueCount++;
    return;
}

02 같지 않는 경우 색종이를 1/2씩 분할하여 모두 같은 색인지 다시 체크하며 재귀적으로 확인

// 같은 색이 아니면 4분할하여 재귀 호출
int newSize = size / 2;
DivideAndConquer(row, col, newSize); // 왼쪽 위
DivideAndConquer(row, col+newSize, newSize); // 오른쪽 위
DivideAndConquer(row+newSize, col, newSize); // 왼쪽 아래
DivideAndConquer(row + newSize, col + newSize, newSize); // 오른쪽 아래

---

using System;
using System.Collections.Generic;

namespace baek2
{
    class Program
    {
        static int[,] paper;
        static int whiteCount = 0;
        static int blueCount = 0;
        static void DivideAndConquer(int row, int col, int size)
        {
            int firstColor = paper[row, col];

            bool isSame= true;
            for (int i = row; i < row + size; i++)
            {
                for (int j = col; j < col + size; j++)
                {
                    if (paper[i, j] != firstColor)
                    {
                        isSame = false;
                        break;
                    }
                }
                if (!isSame)
                    break;
            }

            if (isSame)
            {
                if (firstColor == 0)
                    whiteCount++;
                else
                    blueCount++;
                return;
            }

            // 같은 색이 아니면 4분할하여 재귀 호출
            int newSize = size / 2;
            DivideAndConquer(row, col, newSize); // 왼쪽 위
            DivideAndConquer(row, col+newSize, newSize); // 오른쪽 위
            DivideAndConquer(row+newSize, col, newSize); // 왼쪽 아래
            DivideAndConquer(row + newSize, col + newSize, newSize); // 오른쪽 아래
        }
        public static void Main()
        {
            int n = int.Parse(Console.ReadLine());
            paper = new int[n + 1, n + 1];
            for (int i = 0; i < n; i++)
            {
                int[] token = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
                for (int j = 0; j < n; j++)
                {
                    paper[i, j] = token[j];
                }
            }
            DivideAndConquer(0, 0, n);

            Console.WriteLine(whiteCount);
            Console.Write(blueCount);
        }
    }
}