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

문제 출처 - Programmers

문제는 여기

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

---

[참고]

1. 문제를 다 풀고 틀렸다고 나와 검색을 해봤더니 전역 변수로 선언과 동시에 초기화를 하면 틀리지만 메서드 내부에서 초기화를 해주면 통과를 한다고 하여 해당 방법을 사용하여 문제를 풀었다.

[풀이]

1. 탐색하지 않고 빈칸이라면 영역의 수를 증가시키고 dfs 탐색을 해준다.

2. dfs 탐색을 통해 해당 영역의 총 개수를 구하면서 연결된 영역을 모두 탐색해준다.

3. 가장 큰 영역의 크기를 구하기 위해 최대값을 갱신해준다.

4. 모든 영역을 탐색해준다.

5. 1. 에서 구해지는 영역의 개수와 3. 에서 구해지는 가장 큰 영역의 크기를 배열에 담아 리턴해준다.

[접근]

1. 상하좌우 탐색하는 것을 보고 bfs, dfs를 사용하면 되겠다고 생각하였다.

[코드]

class Solution {
    static int numberOfArea;
    static int maxSizeOfOneArea;
    static int area = 0;
    static boolean[][] check;
    
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    
    public int[] solution(int m, int n, int[][] picture) {
        // 전역에서 초기화 해주면 틀림
        // 내부에서 초기화 해주면 통과
        numberOfArea = 0;
        maxSizeOfOneArea = 0;
        
        int[] answer = new int[2];
        check = new boolean[m][n];
        
        answer[0] = numberOfArea;
        answer[1] = maxSizeOfOneArea;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 0이 아니고, 방문한 적이 없다면
                if (picture[i][j] != 0 && !check[i][j]) {
                    // 영역의 수 1 증가
                    numberOfArea++;
                    // dfs 탐색
                    dfs(i, j, picture);
                }
                // 한 영역의 탐색이 모두 끝났다면, 조건에 따라 최대 영역의 수를 변경.
                maxSizeOfOneArea = area < maxSizeOfOneArea ? maxSizeOfOneArea : area;
                area = 0;
            }
        }
        
        // 15. 각 값을 answer 배열에 담아주고 끝.
        answer[0] = numberOfArea;
        answer[1] = maxSizeOfOneArea;
        
        return answer;
    }

    public static void dfs(int x,int y, int[][] picture) {
        if (check[x][y])
            return;
        
        check[x][y] = true;
        // 영역의 수 증가.
        area++;
        
        // 사방탐색
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            // 범위를 벗어나는지 체크
            if (nx < 0 || nx >= picture.length || ny < 0 || ny >= picture[0].length)
                continue;
            
            // 현재 색 == 상,하,좌,우 색 && 방문한적 없다면.
            if (picture[x][y] == picture[nx][ny] && !check[nx][ny]) {                
                // DFS 탐색
                dfs(nx, ny, picture);
            }            
        }        
    }
}