백준 C# - 1992 +) 풀이

아래 문제와 매우 유사한 문제이다.

백준 C# - 2630 +) 풀이

---

분할 정복 문제이다.

8
11110000
11110000
00011100
00011100
11110000
11110000
11110011
11110011

알고리즘 생각

01 부분 색깔이 모두 같은 색상이어야 한다.

02 그렇지 않는 경우 재귀가 시작한다는 의미로 "("를 출력

03 색종이를 1/2로 나눈 다음 4부분으로 분할한다.

04 재귀가 끝났을 경우 ")" 출력되도록 하면 된다.

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

01 부분 색깔이 모두 같은 색상이어야 한다.

int first = paper[row, col];
bool isSame = true;

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

if(isSame)
{
    sb.Append(first);
    return;
}

02 그렇지 않는 경우 재귀가 시작한다는 의미로 "("를 출력, 색종이를 1/2로 나눈 다음 4부분으로 분할한다. 재귀가 끝났을 경우 ")" 출력되도록 하면 된다.

sb.Append("(");
int newSize = size / 2;
DC(row, col, newSize);
DC(row, col + newSize, newSize);
DC(row + newSize, col, newSize);
DC(row + newSize, col + newSize, newSize);
sb.Append(")");

---

코드 전문

using System;
using System.Collections.Generic;
using System.Text;

namespace baek2
{
    class Program
    {
        static int[,] paper;
        static StringBuilder sb = new StringBuilder();
        public static void DC(int row, int col, int size)
        {
            int first = paper[row, col];
            bool isSame = true;

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

            if(isSame)
            {
                sb.Append(first);
                return;
            }
            sb.Append("(");
            int newSize = size / 2;
            DC(row, col, newSize);
            DC(row, col + newSize, newSize);
            DC(row + newSize, col, newSize);
            DC(row + newSize, col + newSize, newSize);
            sb.Append(")");
        }
        public static void Main()
        {
            int n = int.Parse(Console.ReadLine());
            paper = new int[n + 1, n + 1];
            for(int i = 0; i<n; i++)
            {
                string s = Console.ReadLine();
                for(int j = 0; j<n; j++)
                {
                    paper[i, j] = int.Parse(s[j].ToString());
                }
            }

            DC(0, 0, n);
            Console.WriteLine(sb.ToString());
        }
    }
}