[프로그래머스 level2] 카카오프렌즈 컬러링북

문제

 

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

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

 

풀이

 DFS로  풀 수 있다. 우선 (x,y)와 같은 색인 영역의 수를 구하는 함수를 생각해보자.

 

아래와 같이 색칠판이 있을 때 (3,0)을 기준으로 (3,0)과 같은 색인 영역의 크기를 구해보자. 

(3,0)에서 북, 동, 남, 서 를 차례로 탐색한다.  (3,0)과 이웃한 셀을 (x,y)라고 하자. (x,y)이 (3,0)과 같은 영역으로 분류되려면, 

 

1.  영역내의 셀이어야 한다.

2.  방문한 적이 없는 셀이어야 한다(중복 count 방지) 

3. (3,0)과 같은 색이어야 한다.

 위의 조건을 만족시키면 (x,y)는 (3,0)과 같은 영역의 셀이 된다. 위의 방법대로 탐색을 해보자. 처음에는 (3,0)에서 북쪽으로 이동한다. 이때 3번조건을 충족시키지 못하므로 같은 영역이 아니다. 

이제 동쪽으로 이동해보자 

동쪽의 (3,1)은 위의 1,2,3 조건을 모두 충족하므로 (3,0)과 같은 영역의 셀이다. 그러면 이제 (3,1)에서 다시 호출을 하고 같은 작업을 반복한다. 

 

그럼 여기서 점화식을 세울 수 있는데, f(x,y,color)를 (x,y)를 포함한 이웃 셀 중에서 색깔이 color인 영역의 크기 라고 정의할 수 있다.

 

 따라서 f(x,y,color) 는 (x,y)의 색이 color가 아닌 경우 0, (x,y)의 색이 color인 경우 1 + f(북쪽, color) + f(서쪽, color) + f(남쪽, color) + f(동쪽, color)로 정의된다. 

 

코드

class Solution {
    public static int M;
    public static int N;
    public static boolean[][] visited;
    public static int[][] pictures;
    
    public int[] solution(int m, int n, int[][] picture) {
        int numberOfArea = 0;
        int maxSizeOfOneArea = 0;
        
        
        M = m;
        N = n;
        pictures = picture;
        visited = new boolean[M][N];
        for(int r= 0 ;r<M; r++){
            for(int c= 0 ;c<N; c++){
                if(!visited[r][c] && pictures[r][c] !=0){
                    int sizeOfArea = countArea(r, c, pictures[r][c]);
                    maxSizeOfOneArea = Math.max(sizeOfArea, maxSizeOfOneArea);

                    ++numberOfArea;
                }
            }
        }

        int[] answer = new int[2];
        answer[0] = numberOfArea;
        answer[1] = maxSizeOfOneArea;
        return answer;
    }
    
    public static int countArea(int x, int y, int color){
        if(x<0 || y<0 || x> M-1 || y> N-1){
            return 0;
        }
        else if(pictures[x][y] !=color){
            return 0;
        }
        else if(visited[x][y]){
            return 0;
        }
        else{
            visited[x][y]  = true;
            return 1 + countArea(x-1, y, color) + countArea(x, y+1, color) + countArea(x+1, y, color) + countArea(x, y-1, color);
        }
    }
}