본문 바로가기
알고리즘

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

by minkang 2021. 9. 22.

https://programmers.co.kr/learn/courses/30/lessons1829?language=java 

class Solution {
    public int[] solution(int m, int n, int[][] picture) {
        int numberOfArea = 0;
        int maxSizeOfOneArea = 0;
        boolean[][] visited = new boolean[m][n];
        
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(visited[i][j] == false && picture[i][j] != 0){
                    numberOfArea++;
                    visited[i][j] = true;
                    maxSizeOfOneArea = Math.max(dfs(i, j, m, n, 1, picture, visited), maxSizeOfOneArea);
                }
            }
        }
        
        int[] answer = new int[2];
        answer[0] = numberOfArea;
        answer[1] = maxSizeOfOneArea;
        return answer;
    }
    
    int dfs(int x, int y, int m, int n, int cnt, int[][] picture, boolean[][] visited){
        int[] dx = new int[] {1,-1,0,0};
        int[] dy = new int[] {0,0,1,-1};
        for(int d=0; d<4; d++){
            int nx = x + dx[d];
            int ny = y + dy[d];
            if(nx < 0 || nx >= m || ny<0 || ny>= n || picture[nx][ny] != picture[x][y] || visited[nx][ny] == true){
                continue;
            }
            visited[nx][ny] = true;
            cnt = dfs(nx, ny, m, n, ++cnt, picture, visited);
        }
        return cnt;
    }
    
}

picture 값이 0이 아니고 방문한적이 없을 때 dfs()를 호출하여

플러드 필 방식으로 탐색하였습니다.

각 영역의 최대 갯수는 

                   dfs(4)

                 dfs(3)

               dfs(2)

for(4방향 반복){     

    cnt = dfs(1)

    cnt = dfs(5) 

    cnt = dfs(6)

    cnt = dfs(7)  

}

이런 방식으로 리턴하여 계산했습니다.