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

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

해당 문제는 입력받은 picture의 color 영역의 수와 영역의 최대값을 구하는 문제였습니다. 처음 문제를 봤었을때 DFS 알고리즘 처럼 탐색해 나가는데, basecase는 색깔이 다르거나 방문한 영역인 경우로 산정 하였습니다.
다음 탐색 영역으로는 오른쪽과 아래쪽 영역만 선택하여 DFS을 하도록 하고 초기 테스트 케이스를 통과하였지만 이후 채점 했을 경우에는 통과하지 못했습니다. 어피치의 그림이 그려진 영역을 보면 고민한 결과 시작한 영역의, 상/하/좌/우로 DFS를 진행해야 한다는 것을 알수 있었습니다.

힌트를 얻게 된 어피치 사진

public int[] solution(int m, int n, int[][] picture) {
        boolean[][] visited = new boolean[m][n];
        int[] answer = new int[2];
        long[][] copiedPicture = new long[m][n];
        for (int i =0; i< m; i++) {
            for(int j = 0; j < n; j++) {
                copiedPicture[i][j] = picture[i][j];
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (visited[i][j] == false && copiedPicture[i][j] != 0) {
                    answer[0] = answer[0] + 1;
                    answer[1] = Math.max(answer[1], dfs(copiedPicture, visited, i, j, copiedPicture[i][j]));
                }
            }
        }


        return answer;
    }

    private int dfs(long[][] picture, boolean[][] visited, int m, int n, long color) {
        if (visited[m][n] || picture[m][n] != color) {
            return 0;
        }
        visited[m][n] = true;

        return 1 + dfs(picture, visited, m, Math.max(0, n - 1), color)
                + dfs(picture, visited, Math.min(picture.length - 1, m + 1), n, color)
                + dfs(picture, visited, Math.max(0, m - 1), n, color)
                + dfs(picture, visited, m, Math.min(picture[0].length - 1, n + 1), color);
    }