[Programmers] 카카오프렌즈 컬러링북

2017 카카오 코드 예선

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

---

[DFS or BFS]

다른 방법도 있겠지만 DFS나 BFS를 사용해 '0'이 아닌 곳을 찾고, 같은 숫자로 연결(상,하,좌,우 인접)된 area 개수를 카운트하고, 각 area의 크기(Size)를 구해 최댓값을 도출하면 된다.

 

각 영역의 사이즈를 구하는 방법은 특정 정점을 방문할 때 마다 1을 기본값을 가지고 연결된 지역을 돌며 그 개수만큼 더한 값을 반환한다.

# Code </>

class Solution {

    static int[] Y = {-1,1,0,0}, X = {0,0,-1,1};
    static boolean[][] visit;

    static int DFS(int y, int x, int val, int[][] picture, int m, int n){

        int result = 1;
        visit[y][x] = true;

        for(int a=0; a<4; a++){
            int ny = y+Y[a];
            int nx = x+X[a];

            //범위를 벗어나지 않고 and 방문하지 않은 곳 and 현재 지역의 값과 같은 곳
            if(ny < 0 || nx < 0 || ny > m-1 || nx > n-1 || visit[ny][nx]) continue;
            if(picture[ny][nx] != val) continue;

            result += DFS(ny, nx, val, picture, m, n);
        }

        return result;
    }

    public int[] solution(int m, int n, int[][] picture) {

        visit = new boolean[m][n];
        int maxSize = -1;
        int areas = 0;

        for(int i=0; i<m; i++)
            for(int j=0; j<n; j++)
                if(!visit[i][j] && picture[i][j] != 0){ //방문하지 않았고, 0이 아닌 곳
                    areas++; //방문하지 않은 영역을 찾을 때 마다 영역수 증가
                    int size = DFS(i, j, picture[i][j], picture, m, n);

                    if(maxSize < size)
                        maxSize = size;
                }

        int[] answer = new int[2];
        answer[0] = areas;
        answer[1] = maxSize;
        return answer;
    }
}