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

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

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

풀이과정

전형적인 DFS, BFS 문제라고 생각된다. 문제 풀이는 아래와 같이 진행하였다.

1. (0, 0)부터 시작하여 순차적으로 picture에 속한 모든 원소를 순회한다.
2. 순회 중 임의의 어떤 (i, j)번 째 원소에 대해서, picture[i][j] != 0 이고, visted[i][j] == false 이면 (i, j)번 째 원소는 아직 계산되지 않은 영역이다.
   • 문제에서 주어진 조건에 의해 2차원 배열 picture에 속한 각 원소는 소속된 영역이 없으면 0, 아니면 int 범위 내에 있는 어떤 임의의 정수값을 가진다.
   • 2차원 배열 visited는 picture의 각 원소를 이미 방문(계산) 했는지를 나타내기 위해 별도로 설정 해 준 배열이다.
   • 따라서, 2의 조건을 만족하는 원소를 시작점으로 하여 picture[i][j]와 같은 값을 가지는 원소들을 대상으로 dfs를 돌리면 같은 영역의 원소들을 찾을 수 있다.
     • int value = picture[i][j] 라고 했을 때, DFS 알고리즘에 따라 주변 원소들을 돌면서 picture[a][b] == value 이고, visited[a][b] == false 인 원소들을 카운팅한다.
3. 2의 과정을 picture[i][j] ≠ 0 인 모든 (i, j) 순서쌍에 대해서 모든 visited[i][j] 가 true 가 될 때 까지 반복한다.

이렇게 진행했을 때, 2의 조건에 해당하여 dfs 알고리즘이 돌아가는 원소가 있을 때 마다 새로운 영역을 한 개씩 찾은 것이 되며, 새 영역을 찾을 때 마다 가장 넓은 영역의 넓이를 저장해 줄 수 있다.

 

최종 결과로는 이렇게 구한 영역의 수와 가장 넓은 영역의 넓이를 반환한다.

 

소스코드

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] && picture[i][j] != 0) {
                    numberOfArea++;
                    maxSizeOfOneArea = Math.max(maxSizeOfOneArea, dfs(visited, picture, i, j, picture[i][j]));
                }
            }
        }

        return new int[] {numberOfArea, maxSizeOfOneArea};
    }

    // 상하좌우 이동
    int[][] directions = {
            {-1, 0}, {1, 0}, {0, -1}, {0, 1}
    };

    private int dfs(boolean[][] visited, int[][] picture, int i, int j, int value) {
        int size = 0;
        if (i < 0 || j < 0 || i >= picture.length || j >= picture[0].length || visited[i][j]) {
            return size;
        }

        if (value == picture[i][j]) {
            size++;
            visited[i][j] = true;

            for (int[] direction : directions) {
                size += dfs(visited, picture, i + direction[0], j + direction[1], value);
            }
        }

        return size;
    }
}