[백준 1992] 쿼드트리 (C++)

문제

백준 1992

1992번: 쿼드트리

풀이

입력이 빈칸으로 구분되지 않기 때문에 string 형식으로 받은 뒤 int 형식으로 map에 저장시켜 줍니다.

루프를 돌면서 색깔이 같지 않다면 4분할해주고, 같다면 그 색깔을 출력합니다.

소스 코드

#include<iostream>
#include<string>
using namespace std;
 
int map[65][65];
int N;
 
void fun(int sx, int sy, int size)
{
    int color = map[sy][sx];
    bool issame = true;
    for (int i = sy; i < sy + size; i++)
    {
        for (int j = sx; j < sx + size; j++)
        {
            if (color != map[i][j])
            {
                issame = false;
                break;
            }
        }
        if (!issame)
            break;
    }
 
    //색깔이 똑같으면 출력
    if (issame)
    {
        cout << color;
    }
    else
    {
        // 색깔이 다르면 4분할
        int nsize = size / 2;
        cout << "(";
        //좌상
        fun(sx, sy, nsize);
        //우상
        fun(sx + nsize, sy, nsize);
        //좌하
        fun(sx, sy + nsize, nsize);
        //우하
        fun(sx + nsize, sy + nsize, nsize);
        cout << ")";
    }
}
 
int main()
{
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        string s;
        cin >> s;
        for (int j = 1; j <= s.size(); j++)
        {
            //map에 int 형식으로 저장
            map[i][j] = s[j - 1] - '0';
        }
    }
    fun(1, 1, N);
    return 0;
}