[ 프로그래머스 [ 월간코드챌린지 ] ] 쿼드압축 후 개수 세기 (C++)

프로그래머스의 쿼드압축 후 개수세기(월간코드챌린지) 문제이다.

[ 문제풀이 ]

주어진 맵을 정확히 4개의 균일한 정사각형 영역으로 압축해 나갔을 때, 최종적으로 남아있는 0과 1의 갯수를 구해야 하는 문제이다.

.

그럼 위와 같은 맵을 가지고 한번 진행해보자.

#1. 현재 범위내에 있는 맵의 상태 Check

위와 같은 맵에서 가장 처음에 맵의 상태를 확인한다면, 아마 4 x 4 칸에 대한 상태를 확인하게 될 것이다.

딱 보더라도, 위의 4 x 4 크기의 맵은, 0 혹은 1 하나로만 이루어져 있지 않다.

따라서 위의 맵을 정확하게 4개의 정사각형으로 나누는 과정을 진행하게 될 것이다.

그럼, 정사각형을 나누는 과정은 이 다음 단계에서 구체적으로 알아보도록 하고, 지금부터는 4 x 4 크기에 대한 부분을 확인하는 것에 대해서 이야기를 해보자.

사실, 이렇게 본다면 머리로는 "딱 봐도 처음에는 4x4 크기의 맵을 탐색해봐야 겠다" 라는 것을 알 수는 있지만, 이를 코드로 구현하기 위해서 어떻게 해야 할까 ?? 이 부분에 대해서 알아보자.

본인은 정사각형을 나눌 때에도 항상 "가장 왼쪽 위의 좌표를 기준"으로 삼았다.

즉, 가장 처음에는 (0 , 0)을 기준으로 맵을 바라보게 될 것이다.

그리고, 가로로 4칸, 세로로 4칸이 되는 영역을 탐색을 했는데, 이 '4칸' 이라는 것은 어떻게 알 수 있을까 ??

바로 "주어진 맵의 한 변의 길이"가 된다. 물론 이 길이 또한 정사각형을 나누는 과정에 의해서 계속해서 변하게 되는 값일 것이다. 무튼, 지금까지의 내용을 정리해본다면,

"가장 왼쪽 위의 좌표를 기준으로, 현재 탐색하고자 하는 정사각형의 한변의 길이를 통해서 탐색" 한다는 것이다.

그럼, 탐색을 할 때에는 뭐를 어떻게 탐색해 주어야 할까 ??

우리가 특정 범위를 탐색했을 때, 우리에게 주어질 수 있는 경우의 수는 딱 3가지 밖에 존재하질 않는다.

1. 특정 범위가 모두 '0'인 경우

2. 특정 범위가 모두 '1'인 경우

3. 그게 아닌 경우

이렇게 3가지 밖에 존재하질 않는다. 만약, 1번에 부합하는 경우라면 ?? 더 이상 정사각형을 나누는 과정을 필요로 하지 않는다. 왜 ?? 어차피 모두 0이기 때문에 더 이상 압축이 되질 않기 때문이다.

2번 경우도 마찬가지이다.

정사각형을 잘라야 하는 경우는, 3번 경우가 되는 것이다.

3번 경우에 해당하는 경우, 정사각형을 나누는 과정을 본인은 재귀를 통해서 표현해 주었다.

재귀를 통해서 표현할 때, 필요한 매개변수들은 [ 현재 범위의 가장 왼쪽 위의 좌표 , 현재 범위의 정사각형의 한 변의 길이 ] 를 필요로 할 것이다.

1. 탐색을 진행할 때에는 다음과 같이 2가지 요소가 필요하다.

   1-1) 현재 탐색을 하고자 하는 범위에서, 가장 왼쪽 위의 좌표

   1-2) 현재 탐색을 하고자 하는 정사각형의 한 변의 길이

2. 1번에 의해서 당연히 가장 초기값은 (0 , 0)에서 주어진 맵의 한 변의 길이로 탐색을 시작할 것이다.

3. 탐색을 할 때, 파악해야 하는 것은 다음과 같은 3가지 상태가 있다.

   3-1) 주어진 범위가 모두 0으로 채워져 있는 경우 : 더 이상의 탐색이 필요하지 않다.

   3-2) 주어진 범위가 모두 1로 채워져 있는 경우 : 더 이상의 탐색이 필요하지 않다.

   3-3) 그게 아닌 경우 : 더 이상의 탐색이 필요하다.

#2. 재귀를 이용한 사각형 나누기
.

가장 초기 상태, 즉, (0 , 0)에서 4 x 4 크기의 정사각형을 탐색해 봤을 때는 오로지 0 혹은 1로만 이루어져 있지 않다는 것을

알 수 있다. 즉 ! 위의 정사각형을 정확하게 4개로 분할하는 과정이 필요하다.

그림으로 나타낸다면 위의 사각형을 다음과 같이 4개의 사각형으로 나눌 것이다.

.

위와 같이 나눌 수 있는데, 그럼 이 때 각 사각형의 "가장 왼쪽위의 좌표" 와 "한 변의 길이" 에 대해서 이야기를 해보자.

위의 4개의 사각형들을 왼쪽 위의 사각형을 1번, 오른쪽 위의 사각형을 2번, 왼쪽 아래의 사각형을 3번, 오른쪽 아래의 사각형을 4번 사각형 이라 이름 붙여보자.

각각의 사각형의 [ 가장 왼쪽 위의 좌표 , 한 변의 길이 ] 를 적어보면 다음과 같다.

1번 사각형 : [ (0 , 0) , 2 ]

2번 사각형 : [ (0 , 2) , 2 ]

3번 사각형 : [ (2 , 0) , 2 ]

4번 사각형 : [ (2 , 2) , 2 ]

보다시피, 가장 왼쪽 위의 좌표가 모두 다르다는 것을 알 수 있다. 그럼 이 좌표의 값을 어떻게 구할까 ??

다시 돌아가보자. 우리는 처음에 [ (0 , 0) , 4 ] 라는 사각형에서 위와 같이 4개의 사각형으로 나누게 되었다.

즉, 나누는 순간 "변의 길이는 절반이 된다" 라는 것을 알 수 있다. 이 절반이 된 변의 길이를 K 라고 표현하겠다.

그리고 각 사각형들의 왼쪽 위의 좌표를 이 K를 통해서 적어보면 다음과 같이 표현할 수 있다.

1번 사각형 : [ (0 , 0) , K ]

2번 사각형 : [ (0 , 0 + K) , K ]

3번 사각형 : [ (0 + K , 0) , K ]

4번 사각형 : [ (0 + K , 0 + K) , K ]

이렇게 표현을 할 수가 있다.

그럼 이제는 (0 , 0)이 아닌 (x , y) 라는 좌표에서 생각을 해보자.

(x , y)라는 좌표에서 한 변의 길이가 K인 정사각형을 탐색해 봤더니, 0으로만 이루어져 있지도 않고, 1로만 이루어져 있지도 않은 상태였다고 생각을 해보자. 즉, 사각형을 나눠야 하는 상황이다.

그럼 나눠질 4개의 사각형의 좌표와 한 변의 길이를 적어보면 다음과 같다.

1번 사각형 : [ (x , y) , K / 2 ]

2번 사각형 : [ (x , y + K / 2) , K / 2 ]

3번 사각형 : [ (x + K / 2 , y) , K / 2 ]

4번 사각형 : [ (x + K / 2 , y + K / 2) , K / 2 ]

이렇게 4개의 영역을 재귀를 통해서 탐색을 진행해 주었다.

비슷한 문제로는 백준의 쿼드트리(1992) 문제와 색종이 붙이기(2630) 문제가 있다.

[ 백준 - 쿼드트리(1992) 문제 바로가기 ]

[ 백준 - 쿼드트리(1992) 풀이 바로가기 ]

[ 백준 - 색종이 붙이기(2630) 문제 바로가기 ]

[ 소스코드 ]

#include <string>
#include <vector>
 
using namespace std;
 
vector<vector<int>> MAP;
 
void DFS(int x, int y, int Size, vector<int> &answer)
{
    bool Zero, One;
    Zero = One = true;
    for (int i = x; i < x + Size; i++)
    {
        for (int j = y; j < y + Size; j++)
        {
            if (MAP[i][j] == 0) One = false;
            if (MAP[i][j] == 1) Zero = false;
        }
    }
 
    if (Zero == true)
    {
        answer[0]++;
        return;
    }
    if (One == true)
    {
        answer[1]++;
        return;
    }
 
    DFS(x, y, Size / 2, answer);
    DFS(x, y + Size / 2, Size / 2, answer);
    DFS(x + Size / 2, y, Size / 2, answer);
    DFS(x + Size / 2, y + Size / 2, Size / 2, answer);
}
 
vector<int> solution(vector<vector<int>> arr) 
{
    vector<int> answer(2, 0);
    MAP = arr;
    DFS(0, 0, arr.size(), answer);
    return answer;
}