문제 링크

1992 쿼드트리
실버 1
탐색, 분할정복

풀이

좌표를 네부분으로 나누어서 탐색하다가 다른 숫자가 나오면 압축 불가하므로 다시 그부분을 네부분으로 바꾸는 재귀구조로 만들었다.

실수 포인트

문제를 제대로 읽지않아서 괄호를 어떨때 쳐야하는지 몰랐다.
이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다
압축한 결과만 괄호에 넣어야하므로
0000
0000
0000
0000
일때 0을 출력 해야했다.

코드 (java)

import java.util.Scanner;
import java.util.Stack;

public class 백준1992 {
    public static Scanner scan=new Scanner(System.in);
    public static StringBuilder stk=new StringBuilder();
    static int n;
    static char [][] arr;
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        n=scan.nextInt();
        arr=new char[n][n];
        char a = 0;
        int cnt=0;
        for(int i=0;i<n;i++) {
            String str=scan.next();
            for(int j=0;j<n;j++) {
                arr[i][j]=str.charAt(j);
                if(i==0&&j==0) {
                    a=arr[i][j];
                }else {
                    if(a==arr[i][j]) {
                        cnt++;
                    }
                }
            }
        }
        if(cnt+1==n*n) System.out.println(arr[0][0]);
        else {
            sol(0,0,n);
            System.out.println(stk);

        }

    }
    public static void sol(int startx,int starty, int n) {
        char leftUp=arr[startx][starty],leftDown=arr[startx+n/2][starty],rightUp=arr[startx][starty+n/2],rightDown=arr[startx+n/2][starty+n/2];
        stk.append('(');

        boolean a=true,b=true,c=true,d=true;
        //왼쪽위
        for(int i=startx;i<startx+n/2;i++) {
            for(int j=starty;j<starty+n/2;j++) {
                if(a==false)break;

                if(arr[i][j]!=leftUp) {
                    sol(startx,starty,n/2);
                    a=false;
                    break;
                }
            }
            
        }
      

        if(a) {
            stk.append(leftUp);
        }
        
        //오른쪽위
        for(int i=startx;i<startx+n/2;i++) {
            for(int j=starty+n/2;j<starty+n;j++) {
                if(b==false)break;

                if(arr[i][j]!=rightUp) {
                    sol(startx,starty+n/2,n/2);
                    b=false;
                    break;
                }
            }
        }
        if(b) stk.append(rightUp);

        //왼쪽 아래
        for(int i= startx+n/2;i<startx+n;i++) {
            for(int j=starty;j<starty+n/2;j++) {
                if(c==false)break;

                if(arr[i][j]!=leftDown) {
                    sol(startx+n/2,starty,n/2);
                    c=false;
                    break;
                }
            }
        }
        if(c) stk.append(leftDown);

        //오른쪽 아래
        for(int i=startx+n/2;i<startx+n;i++) {
            for(int j=starty+n/2;j<starty+n;j++) {
                if(d==false)break;
                if(arr[i][j]!=rightDown) {
                    sol(startx+n/2,starty+n/2,n/2);
                    d=false;
                    break;                                                                                                       
                }

            }
        }
        if(d) {
            stk.append(rightDown);
        }
       
        stk.append(')');


    }

}