📒활용개념

DFS를 이용하여 각각의 부분을 확인한다.

📌문제설명

0과 1로 이루어진 2n x 2n 크기의 2차원 정수 배열 arr이 있습니다. 당신은 이 arr을 쿼드 트리와 같은 방식으로 압축하고자 합니다. 구체적인 방식은 다음과 같습니다.

• 당신이 압축하고자 하는 특정 영역을 S라고 정의합니다.
• 만약 S 내부에 있는 모든 수가 같은 값이라면, S를 해당 수 하나로 압축시킵니다.
• 그렇지 않다면, S를 정확히 4개의 균일한 정사각형 영역으로 쪼갠 뒤, 각 정사각형 영역에 대해 같은 방식의 압축을 시도합니다.

배열에 최종적으로 남는 0과 1의 개수를 배열에 담아서 return하여라.

📌구현

#include <string>
#include <vector>
#include <iostream>

using namespace std;

vector<vector<int>> map;					//부분의 정보를 판단하는 map
vector<int> answer(2);

void dfs(int x, int y, int size){
    int cur;								//가장 앞쪽의 수
    bool check=true;						//모두 같은 수인지 판단
    cur=map[x][y];
    
    for(int i=x; i<x+size; i++){
        for(int j=y; j<y+size; j++){
            if(cur!=map[i][j]){
                check=false;				//하나라도 다른 수가 있으면 더이상 검사할 필요가 없음
                break;
            }
        }
        if(!check){
            break;
        }
    }
    if(check){								//모두 같은 수라면 answer++
        answer[cur]++;
    }
    else{
        dfs(x,y,size/2);					//upper left
        dfs(x+size/2, y, size/2);			//lower left
        dfs(x, y+size/2, size/2);			//upper right
        dfs(x+size/2, y+size/2, size/2);	//lower right
    }
    
}

vector<int> solution(vector<vector<int>> arr) {
    map=arr;
    dfs(0,0,arr.size());
    return answer;
}

📌주의점

• dfs에 대하 개념 필요
• dfs함수 구현에 필요한 변수가 무엇인지 구할 수 있어야 한다.