[Programmers]#Level2_쿼드압축 후 개수 세기, 분할-정복, DFS

#1. 문제

프로그래머스

 

---

 

#2. 풀이

 

1. DFS

[자료구조]#6_그래프

DFS는 그래프의 모든 정점을 탐색하는 방법 중 하나입니다. DFS는 현재 경로에서 더 이상 확장 불가능한 단말 노드까지 깊이 우선적으로 탐색합니다. 일반적으로, DFS는 재귀 호출 혹은 스택 자료구조를 통해 구현합니다.

 

2. 분할-정복

[알고리즘]#4_분할-정복 알고리즘

분할-정복은 현재 문제를 작은 하위 문제들로 분할하여, 이를 재귀적으로 해결합니다. 그리고, 분할된 부분 문제들에서 찾은 해를 결합하여 최적해를 찾아는 알고리즘 기법입니다.

 

3. 기저 조건 확인 후 분할-정복!

1. 먼저, 분할-정복 기반의 dfs를 설계합니다.
2. 기저 조건을 확인합니다. 현재 사각형의 크기가 1이거나 혹은 압축 가능한 상태인지 확인합니다.
3. 다음으로, 현재 주어진 2ⁿ x 2ⁿ 크기의 사각형을 총 4개로 분할합니다.
4. 위 작업을 재귀적으로 수행하며, 최적해를 찾습니다.

 

---

 

#3. 코드

/*
    @링크: https://school.programmers.co.kr/learn/courses/30/lessons/68936
    @문제: S영역에 대한 쿼드 압축 진행 후 배열에 최종적으로 남은 0의 개수와 1의 개수
    @설명
        1. 분할-정복
        - 분할: 균일한 4개의 정사각형으로 분할
        - 정복: 현재 사각형에 대하여 조건 합치 여부 검사 수행하고 정답 업데이트 혹은 분할 계속 진행
*/

#include <string>
#include <vector>

using namespace std;

typedef pair<int,int> p;

vector<int> answer(2,0);

bool checkEnableCompression(p square, int size, const vector<vector<int>>& arr)
{
    //@사이즈 만큼 검사
    int cy = square.first;
    int cx = square.second;

    bool bEnableComp = true;
    int val = arr[cy][cx];
    for(int i = cy; i < cy+size; ++i)   
    {
        for(int j = cx; j < cx+size; ++j)
        {
            if(val != arr[i][j])
            {
                bEnableComp = false;
                break;
            }
        }
    }
    return bEnableComp;
}

void quadComp(p start, int size, vector<vector<int>>& arr)
{
    int cy = start.first;
    int cx = start.second;
    //@종료 조건
    //1. size가 1일 경우
    if(size == 1)
    {
        answer[arr[cy][cx]]++;
        return;
    }
    //2. 영역 내 모든 수가 같을 경우
    if(checkEnableCompression(start, size, arr))
    {
        answer[arr[cy][cx]]++;
        return;
    }
    //@분할-정복
    quadComp({cy, cx}, size/2, arr);
    quadComp({cy, cx+size/2}, size/2, arr);
    quadComp({cy+size/2, cx}, size/2, arr);
    quadComp({cy+size/2, cx+size/2}, size/2, arr);
}

vector<int> solution(vector<vector<int>> arr) {

    //@시작 크기
    int col = arr.size();
    //@크기가 1일 경우
    if(col < 2)
    {
        int val = arr[0][0];

        if(val == 0) answer[0]++;
        else answer[1]++;

        return answer;
    }
    //@쿼드 압축: 시작 0, 정사각형 크기 col
    quadComp({0,0}, col, arr);

    return answer;
}

 

---