Java - [프로그래머스 Lv.2]17684 - 쿼드압축 후 개수 세기

출처

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

문제

주어진 2의 n제곱의 길이를 가진 맵에서, 한 영역이 모두 같은 숫자로 이루어질 때 까지 4등분해 나가는 문제입니다. 그림을 보면 이해가 쉽습니다.

입출력 예는 위와 같이 생겼습니다. 이것을 보고 우리는 풀이 단계를 떠올릴 수 있습니다.

1. 먼저 현재 영역이 모두 같은수인지 판단

public boolean isSame(int[][] arr, int x, int y, int len) {
        int tmp = arr[x][y];
        for (int i = x; i < x + len; i++) {
            for (int j = y; j < y + len; j++) {
                if (arr[i][j] != tmp) {
                    return false;
                }
            }
        }
        return true;
    }

현재 탐색의 기준점이 되는 좌표 x,y와 탐색 영역의 길이인 len 변수를 통해 해당 영역이 모두 같은 숫자로 이루어져 있는지 판단합니다.

2-1. 현재 영역이 모두 같다면

현재 영역이 모두 같다면, answer 배열 해당하는 숫자에 +1을 해주어 정답을 기록합니다.

if (isSame(arr, x, y, len)) {
            answer[arr[x][y]]++;
            return;
        }

2-2. 현재 영역이 같지 않다면 4등분

현재 영역이 모두 같지 않기때문에, 우리는 4번의 dfs를 실행시켜 4개 영역으로 나누어 탐색을 진행해야 합니다.

dfs(arr, x, y, len/2); // 현재 영역의 왼쪽 위 영역 
dfs(arr, x + len/2, y, len/2); // 현재 영역의 오른쪽 위 영역
dfs(arr, x, y + len/2, len/2); // 현재 영역의 왼쪽 아래 영역
dfs(arr, x + len/2, y + len/2, len/2); // 현재 영역의 오른쪽 아래 영역

이렇게 총 4번의 dfs로 진입하게 됩니다.

코드

import java.util.*;
class Solution {
    public int[] answer = new int[2];
    
    public int[] solution(int[][] arr) {
        dfs(arr, 0, 0, arr.length);
        return answer;
    }
    
    public void dfs(int[][] arr, int x, int y, int len) {
        if (isSame(arr, x, y, len)) {
            answer[arr[x][y]]++;
            return;
        }
        dfs(arr, x, y, len/2);
        dfs(arr, x + len/2, y, len/2);
        dfs(arr, x, y + len/2, len/2);
        dfs(arr, x + len/2, y + len/2, len/2);
    }
    
    public boolean isSame(int[][] arr, int x, int y, int len) {
        int tmp = arr[x][y];
        for (int i = x; i < x + len; i++) {
            for (int j = y; j < y + len; j++) {
                if (arr[i][j] != tmp) {
                    return false;
                }
            }
        }
        return true;
    }
}