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

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

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

 

• 그래프탐색 문제이다.
• DFS 탐색 횟수와 깊이가 문제의 정답이다.

 

class Solution {

    public static int numOfArea = 0;

    public int[] solution(int m, int n, int[][] picture) {
        int[] answer = new int[2];

        boolean[][] visit = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (visit[i][j] == false && picture[i][j] != 0) {
                    dfs(i, j, picture, picture[i][j], visit);
                    answer[0] += 1;
                    answer[1] = Math.max(answer[1], numOfArea);
                    numOfArea = 0;
                }
            }
        }

        return answer;
    }

    private void dfs(int i, int j, int[][] picture, int color, boolean[][] visit) {
        if (i > picture.length - 1 || i < 0) return;
        if (j > picture[0].length - 1 || j < 0) return;
        if (visit[i][j] == true) return;
        if (picture[i][j] != color) return;

        visit[i][j] = true;

        numOfArea += 1;

        dfs(i + 1, j, picture, color, visit);
        dfs(i - 1, j, picture, color, visit);
        dfs(i, j + 1, picture, color, visit);
        dfs(i, j - 1, picture, color, visit);
    }
}