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

• 문제 링크 : 카카오 프렌즈 컬러링북

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

 

정답

class Solution {
    private int[] x = {1, -1, 0, 0};
    private int[] y = {0, 0, 1, -1};
    private int temp = 0;

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

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

        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(picture[i][j] != 0 && !v[i][j]){
                    numberOfArea++;
                    dfs(v, picture, i, j, m, n);
                }

                if(temp > maxSizeOfOneArea){
                    maxSizeOfOneArea = temp;
                }
                temp = 0;
            }
        }

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

        return answer;
    }

    private void dfs(boolean[][] v, int[][] picture, int i, int j, int m, int n){
        if(v[i][j]){
           return; 
        }

        v[i][j] = true;

        temp++;

        for(int k=0; k<4; k++){
            int nI = i + x[k];
            int nJ = j + y[k];

            if(0 <= nI && nI < m && 0 <= nJ && nJ < n){
                if(picture[i][j] == picture[nI][nJ] && !v[nI][nJ]){
                    dfs(v, picture, nI, nJ, m, n);
                }
            }
        }
    }
}

 

분석

• dfs 문제였다
• 각 칸마다 dfs를 상하좌우에 대해 수행하면서 방문하지 않을 칸을 찾아 재귀적으로 반복하여 풀면 된다.
• 상하좌우를 x좌표 {1, -1, 0, 0} y좌표 {0, 0, 1, -1} 의 배열로 생각하여 푸는 테크닉이 필요하다.
• 또한 상하좌우로 움직였을때 존재하는 칸을 벗어나지 않는 범위에서 수행하여야 한다.

 

참조

[프로그래머스,Level 2] 카카오프렌즈 컬러링북(JAVA 구현)