[C++로 풀이] 쿼드압축 후 개수 세기 (DFS) ⭐⭐

📌 쿼드압축 후 개수 세기

난이도 ⭐⭐

🚀 문제

🚀 내 풀이 ⭕

#include <string>
#include <vector>

using namespace std;

void DFS(vector<vector<int>>& arr, int& zero, int& one, int startRow, int startCol, int n){
    if (n == 1){
        if(arr[startRow][startCol] == 1) one++;
        else zero++;
        return;
    }
    
    int sum = 0;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            sum += arr[startRow + i][startCol + j];
    
    if (sum == 0){
        zero++;
        return;
    }
    else if (sum == n * n){
        one++;
        return;
    }
    else{
        DFS(arr, zero, one, startRow, startCol, n / 2);
        DFS(arr, zero, one, startRow, startCol + n / 2, n / 2);
        DFS(arr, zero, one, startRow + n / 2, startCol, n / 2);
        DFS(arr, zero, one, startRow + n / 2, startCol + n / 2, n / 2);
    }
}

vector<int> solution(vector<vector<int>> arr) {
    vector<int> answer(2, 0);
    DFS(arr, answer[0], answer[1], 0, 0, arr.size());
    return answer;
}

• 하나의 큰 사각형(길이 n) 에서 그림 속 1 -> 2 -> 3-> 4 작은 사각형(길이 n/2) 순으로 깊이 들어간다.
  • 즉, 1 번 사각형 깊이 들어갈 수 있을 때까지 최대한 들어가고 다 끝나고 다 빠져나오면 그제서야 2 번 사각형 DFS.
  • DFS 는 4 개가 진행된다. (매 사각형의 쪼개지는 영역이 4개)
• one에 1의 개수를, zero에 0의 개수를 저장.
• DFS “종료” 조건
  • 1️⃣ n이 1이 될 때
    • 쪼개질 사각형이 더 이상 없이 사각형 내의 원소도 딱 하나 뿐이기 때문에 이게 1인지 0 인지 구분 후 one 혹은 zero 카운팅하고 빠져나오면 된다.
  • 2️⃣ 현재 사각형 내의 모든 원소가 같을 때
    • 모든 원소가 같다면 압축이 가능한 것이므로 DFS 더 들어갈 필요 없이 종료
    • 사각형 내의 모든 원소가 0 으로 같다면 원소들을 모두 더했을 떄 이 0이 될 것이다.
    • 사각형 내의 모든 원소가 1 으로 같다면 원소들을 모두 더했을 떄 이 n * n이 될 것이다. (ex 4길이의 정사각형이라면 모든 원소가 1이라면 합이 16이 될 것.)
• DFS
  • 조건
    • n이 1도 아니라 더 쪼갤 사각형이 있고
    • 해당 사각형 내의 원소들이 전부 같은게 아닐 떄
  • 4 개의 작은 사각형은 각각 시작점(사각형의 좌상단)이 다르다.
    • 첫 번째 사각형의 시작점 👉 [startRow, startCol] (큰 사각형과 동일)
    • 두 번째 사각형의 시작점 👉 [startRow, startCol + n/2]
    • 세 번째 사각형의 시작점 👉 [startRow + n/2, startCol]
    • 네 번째 사각형의 시작점 👉 [startRow + n/2, startCol + n/2]

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기