[1992] - 쿼드트리

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

1992번: 쿼드트리

쿼드 트리 - 각 노드마다 자식이 4개인 트리

재귀문제같은데 왜 쿼드트리인지 모르겠다.

 

문제 풀이

• 범위를 탐색하며 전부 1이면 1, 0이면 0, 그 둘다 아니면 4개로 쪼개서 재귀한다.
• 재귀 하기전 "(" 괄호를 열어주고, 끝나고 ")"를 해주어야 안까지 알아서 채워진다.

using System;
using System.Collections.Generic;
using System.Drawing;
using System.Linq;
using System.Text;

namespace Baekjoon.silver
{
    class _1992
    {
        static int[,] color;
        static StringBuilder stb = new StringBuilder();
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            color = new int[n,n];
            for (int i = 0; i < n; i++)
            {
                string s = Console.ReadLine();
                for (int j = 0; j < n; j++)
                    color[i,j] = int.Parse(s[j].ToString());
            }

            find_str(0, 0, n);
            Console.WriteLine(stb);
        }

        static void find_str(int x, int y, int n) //x 위아래, y 왼오
        {
            if (n < 1)
                return;

            bool iszero = true;
            bool isone = true;
            for (int i = x; i < x + n; i++)
            {
                for (int j = y; j < y + n; j++)
                {
                    if (color[i,j] == 1)
                        iszero = false;
                    else
                        isone = false;
                }
            }

            if (isone)
            {
                stb.Append("1");
            }
            else if (iszero)
            {
                stb.Append("0");
            }
            else
            {
                n /= 2;
                stb.Append("(");
                find_str(x, y, n); // 좌측 상
                find_str(x, y + n, n); // 우측 상
                find_str(x + n, y, n); // 좌측 하
                find_str(x + n, y + n, n); // 우측 하
                stb.Append(")");
            }
        }
    }
}