2630. 색종이 만들기

문제

제한조건

입출력 예시

---

C#

알고리즘의 분할 정복과 재귀가 있어 그대로 이용하도록 했다.

중요한 점은 재귀 함수를 돌릴 때 원하는 위치의 정사각형 범위로 이동할 수 있어야 하는 점이라고 생각함.! → 정사각형을 1/2씩 쪼개면서 같은 색으로 칠해져 있는지 확인하는 방법으로 프로그램을 작성함

using System;

internal class Program
{
	static void Main(string[] args)
	{
		int size = int.Parse(Console.ReadLine());

		int[, ] paper = new int[size, size];
		for (int i = 0; i < size; i++)
		{
			string dataStr = Console.ReadLine();
			var data = dataStr.Split(" ");

			for (int j = 0; j < size; j++)
				paper[i, j] = Convert.ToInt32(data[j]);
		}

		int white = 0;
		int blue = 0;
		CheckedPaper(paper, 0, 0, size, ref white, ref blue);

		Console.WriteLine(white);
        Console.WriteLine(blue);
    }
	
	static void CheckedPaper(int[,] paper, int width, int height, int size, ref int white, ref int blue)
	{
        if (size == 1)
		{
			if (paper[height, width] == 0) { white++; }
			else { blue++; }
			return;
		}

		int color = paper[height, width];
		if (IsSameColor(paper, width, height, size)) 
		{
			if (color == 0) { white++; }
			else { blue++; }
			return;
		}

		CheckedPaper(paper, width, height, size / 2, ref white, ref blue);
		CheckedPaper(paper, width, height + size / 2, size / 2, ref white, ref blue);
		CheckedPaper(paper, width + size / 2, height, size / 2, ref white, ref blue);
		CheckedPaper(paper, width + size / 2, height + size / 2, size / 2, ref white, ref blue);
	}

	static bool IsSameColor(int[,] paper, int width, int height, int size)
	{
		int color = paper[height, width];

		for (int i = 0; i < size; i++)
			for(int j = 0; j < size; j++)
				if (color != paper[height + i, width + j])
					return false;

		return true;
	}
}

[성공]

---

백준에서 문제 확인