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

문제 설명

 

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

 

 

풀이 회고

해당 문제는 DFS를 통해 해결할 수 있었습니다. 우선 해당 문제에서 요구하는 것은 '그림의 영역 개수'와 '가장 큰 영역의 칸수'입니다. 이를 구하기 위해 문제에 접근한 방식으로는 다음과 같습니다.

 

1. 주어진 2차원 배열을 차례대로 순회한다.

2. 방문되지 않은 색칠된 영역이라면(배열 요소 값이 0이 아닌 경우) 해당 색의 영역을 DFS 탐색한다.(영역 칸수 카운팅)

3. '2번'에서 모든 탐색을 마친 후 다음 요소 값을 기준으로 다시 DFS 탐색한다.(2번 반복)

 

'2번'에서 DFS 탐색 시 노드 하나 하나는 색칠된 칸수를 의미합니다. 따라서 노드 하나 하나 방문할 때마다 방문 처리 해주면서 해당 색 영역의 칸수를 카운팅해주었습니다. 또한 '3번'에서 다음 요소 값이 방문되지 않았으며 아울러 색칠된 영역이라면 해당 영역은 기존에(2번에서) DFS 탐색했던 영역과 별개의 색으로 색칠된 영역으로 볼 수 있으므로 '그림의 영역 개수(numberOfArea)'를 카운팅해주었습니다.

 

 

소스 코드

class Solution {

    int numberOfArea = 0;
    int maxSizeOfOneArea = 0;
    int temp = 0;
    int m, n;
    int[][] picture;
    boolean[][] visited;

    public int[] solution(int m, int n, int[][] picture) {
        this.m = m;
        this.n = n;
        this.picture = picture;
        visited = new boolean[m][n];

        for (int i = 0; i < m ; i++) {
            for (int j = 0; j < n; j++) {
                if (!visited[i][j] && picture[i][j] != 0) {
                    dfs(i, j, picture[i][j]);
                    numberOfArea++;
                    maxSizeOfOneArea = maxSizeOfOneArea < temp ? temp : maxSizeOfOneArea;
                    temp = 0;
                }
            }
        }

        int[] answer = new int[2];
        answer[0] = numberOfArea;
        answer[1] = maxSizeOfOneArea;

        return answer;
    }

    public void dfs(int x, int y, int color) {
        if (x < 0 || x > m - 1 || y < 0 || y > n - 1 || visited[x][y] || color == 0 || color != picture[x][y]) {
            return;
        }

        visited[x][y] = true;
        temp++;

        dfs(x - 1, y, color);
        dfs(x + 1, y, color);
        dfs(x, y - 1, color);
        dfs(x, y + 1, color);
    }
}

 

 

참고자료

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