[프로그래머스] 쿼드압축 후 개수 세기 C++ 풀이 및 해설

https://school.programmers.co.kr/learn/courses/30/lessons/68936

프로그래머스

풀이 방법

길이 4인 2차원 배열로 풀이 로직을 설명하겠다.

 

처음엔 [0][0]에서 길이 4만큼 검사를 시작한다.

여기서 검사란 [0][0]에서 시작 위치 포함하여 길이 4만큼 우측 아래로 시작 위치의 값과 동일한지 체크하는것이다.

[0][0]에서 길이 4만큼 검사하여 일치하지 않으니 이제 쪼갠다.

 

이제 검사 길이는 4의 절반인 2로 바뀌고 시작 위치를 동그라미친 부분으로 쪼갠다.

각 시작 위치에서 길이 2만큼 검사를 시작하면된다.

 

 

두번째 시작 위치는 검사시 0으로 다 동일하므로 이제 검사할 필요가 없다.

1, 3, 4번째 시작 위치는 검사에서 통과하지 못했다.

이제 각 시작위치에서 또 4 부분으로 시작 위치를 쪼개고 검사를 시작한다.

 

각 위치마다 4분할을하면 위의 그림처럼 시작 위치가 12개가 된다.

이제 각 시작 위치에서 검사는 통과한다.

 

위의 과정이 내가 설계한 로직이다.

이제 코드를 보면 더욱 이해가 가지 않을까싶다.

 

전체 코드

#include <string>
#include <vector>
#include <iostream>
using namespace std;

void recursion(vector<vector<int>> &arr, int x, int y, int n, pair<int, int> &p) {
    
    // 위치 arr[y][x]에서 arr[y+n][x+n]까지 arr[y][x]의 값과 동일한지 체크.
    for(int i=y; i<y+n; i++) {
        for(int j=x; j<x+n; j++) {
            if(arr[y][x] != arr[i][j]) { // 시작점 값과 다르다면 4분할
                // 모두 n의 길이는 절반이 된다. 다음 좌표는 모두 각각 n/2를 더한 위치가 된다.
                recursion(arr, x, y, n/2, p);
                recursion(arr, x+n/2, y, n/2, p);
                recursion(arr, x, y+n/2, n/2, p);
                recursion(arr, x+n/2, y+n/2, n/2, p);
                return; // 일치하지 않는다면 위의 쪼갠 순환호출만 수행하고 반복문을 더 돌리지 않는다.
            }
        }
    }
    
    // 이까지 온것은 시작지점 [y][x] 부터 길이 n만큼 모두 값이 동일하다는 것임.
    if(arr[y][x]==0) // 시작 지점의 값이 0이면 p의 첫번째 값을 +1
        p.first++;
    else
        p.second++;
}

vector<int> solution(vector<vector<int>> arr) {
    vector<int> answer;
    pair<int,int> p;
    recursion(arr, 0, 0, arr.size(), p); // 첫 검사 길이는 배열의 길이이다.
    answer.push_back(p.first);
    answer.push_back(p.second);
    return answer;
}