프로그래머스 lv2 카카오프렌즈 컬러링북

링크

카카오 프렌즈 컬러링북

풀이

class Solution {
    public int[] solution(int m, int n, int[][] picture) {
        int numberOfArea = 0;
        int maxSizeOfOneArea = 0;
        int areaCnt = 0;

        // 문제가 원본배열에 수정을 가하면 틀리다고 나온다.
        int[][] copy = new int[picture.length][picture[0].length];
        for (int i = 0; i < picture.length; i++) { // 반복문 + ArrayCopy
            System.arraycopy(picture[i], 0, copy[i], 0, copy[i].length);
        }

        for (int i = 0; i < copy.length; i++) {
            for (int j = 0; j < copy[i].length; j++) {
                if (copy[i][j] != 0) {
                    areaCnt = getAreaCnt(copy, i, j, copy[i][j]);
                    maxSizeOfOneArea = Math.max(maxSizeOfOneArea, areaCnt);
                    if (areaCnt != 0) numberOfArea++;
                }
            }
        }

        int[] answer = new int[2];
        answer[0] = numberOfArea;
        answer[1] = maxSizeOfOneArea;
        return answer;
    }

    public int getAreaCnt(int[][] arr, int i, int j, int color) {
        if (i < 0 || j < 0 || i >= arr.length || j >= arr[i].length || arr[i][j] != color) return 0;
        arr[i][j] = 0; // 다음 탐색시에 카운팅되면 안되니까..
        return 1 + getAreaCnt(arr, i - 1, j, color)
                + getAreaCnt(arr, i + 1, j, color)
                + getAreaCnt(arr, i, j + 1, color)
                + getAreaCnt(arr, i, j - 1, color);
    }
}

소감

• 재귀함수를 만들어서 풀어보았다.
• 테스트케이스는 통과하는데, 정작 제출시에는 통과가 안되어서 찾아보니...원본 배열을 수정하면 안된다고 한다.
• 그래서 배열을 복사해야만 했다.
• 추가로 해당 문제를 DFS, BFS로 푸는 방법도 있는 것 같던데... 관련해서 공부가 필요할 듯 하다.