[카카오] 카카오 프렌즈 컬러링북 (java)

문제링크

https://programmers.co.kr/learn/courses/30/lessons/1829

코딩테스트 연습 - 카카오프렌즈 컬러링북

문제풀이

👨🏻‍💻 핵심 스킬 👨🏻‍💻
 브루트 포스

문제에서는 영역의 개수와, 영역의 최대값을 물어보고 있다. 영역은 색칠을 해야하는 부분의 상하좌우 중 연결된 동일한 색상이어야 하며 0의 경우색칠을 하지 않는다. 따라서 나는 체크하는 배열을 만들어, 체크가 안된 부분 중 0이 아닌 부분을 체크하며 영역을 구분지었다. 

$n*m$크기의 배열을 모두 돌면서 아직 확인을 안한 부분이 있으면 그 부분과 연결되어있는 4방면을 체크하여 확인하여준다. 체크는 재귀를 활용하여 수행해주었다. 모두 다 체크하였다면 다시 체크배열에서 체크가 안된 부분이 있는지 확인한다. 만약 체크가 안되어 있다면 해당 영역과 별개의 영역이기 때문에 위에서 설명한 작업을 반복하여 준다. 체크배열의 끝까지 모두 체크를 하였다면 최종적으로 영역의 수와 영역의 개수의 최대값을 구할 수 있다.

 

구현코드

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

        boolean[][] check = new boolean[m][n];

        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(!check[i][j] && picture[i][j] != 0) {
                    int count = group(i, j, picture, check);
                    if(maxSizeOfOneArea < count){
                        maxSizeOfOneArea = count;
                    }
                    numberOfArea++;
                }
            }
        }

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


    private int group(int x, int y, int[][] picture, boolean[][] check) {
        check[x][y] = true;
        int count = 1;
        int[] dx = {-1,0,1,0};
        int[] dy = {0,1,0,-1};

        for(int z = 0; z < 4; z++){
            int checkX = x + dx[z];
            int checkY = y + dy[z];
            if(checkX >= 0 && checkX < picture.length && checkY >= 0 && checkY < picture[0].length){
                if(check[checkX][checkY])
                    continue;
                if(picture[checkX][checkY] == picture[x][y])
                    count += group(checkX,checkY,picture,check);
            }
        }
        return count;
    }
}

 

시간복잡도

체크배열만큼 돌아가므로 $O(m*n)$이다.

잘못된 지식이나 궁금한 내용이 있을 경우 편하게 댓글 남겨주시면 감사하겠습니다 :)