[알고리즘 / 프로그래머스] 카카오프렌즈 컬러링북

programmers.co.kr/learn/courses/30/lessons/1829

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

 

문제는 위와 같으며, 이 문제는 DFS 를 통해 해결할 수 있습니다.

 

시작지점과 끝 지점이 있는 것이 아니기 때문에 전체 컬러링북의 크기인 m x n (1 <= m, n <= 100) 을 모두 확인하며 같은 영역에 해당하는 칸 수가 몇개인지 확인합니다.

 

예제를 살펴보면 먼저 컬러링 북의 영역을 나타내는 이차원 배열을 만들고 값을 저장합니다. 또한 해당 칸을 방문한 적이 있는지 확인하는 배열을 만들고 0으로 초기화 합니다.

 

현재 위치를 기준으로 "아래, 위, 우, 좌" 순서대로 컬러링북 범위 내에 존재하고 방문한 적이 없으며, 현재 위치 값과 같은 경우 (같은 색으로 칠해진 경우) 같은 영역에 해당하므로 연관된 영역 값으로 추가(방문할 수 있는 경우의 수를 추가)합니다.

방문 과정 확인.gif

최종 방문 결과

 

그리고 이렇게 반환된 값은 하나의 영역안에 포함된 칸의 수이므로 영역 값을 +1 하고, 최대 칸 수와 비교하여 더 큰 값을 저장합니다.

 

자바 코드는 다음과 같습니다.

class Solution {
    private static int[] dx = {1, -1, 0, 0};
    private static int[] dy = {0, 0, 1, -1};

    private static int mm;
    private static int nn;
    private static int[][] pictures;
    private static int[][] visited;
    
    public int[] solution(int m, int n, int[][] picture) {
        int numberOfArea = 0;
        int maxSizeOfOneArea = 0;
        
        mm = m;
        nn = n;
        pictures = picture;

        visited = new int[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (picture[i][j] == 0) { // 색칠 칸이 아닌 경우 패스
                    continue;
                }

                if (visited[i][j] == 0) { // 색칠 칸이지만 방문한 적이 없는 경우
                    int num = dfs(i, j);
                    numberOfArea += 1;  // 색칠된 경우 영역이므로 +1
                    maxSizeOfOneArea = Math.max(maxSizeOfOneArea, num);  // 영역에 포함된 칸 수와 기존 최대 칸 수를 비교해서 최대 값 저장
                }
            }
        }

        int[] answer = new int[2];
        answer[0] = numberOfArea;
        answer[1] = maxSizeOfOneArea;
        return answer;
    }
    
    private static int dfs(int x, int y) {
        visited[x][y] = 1;  // 처음 방문한 경우 1
        for (int i = 0; i < 4; i++) { // 아래, 위, 우, 좌 순서로 확인
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx >= 0 && nx < mm && ny >= 0 && ny < nn) {  // 컬러링 북 범위 내에서
                if (visited[nx][ny] == 0 && pictures[x][y] == pictures[nx][ny]) {  // 방문한 적이 없으면서 같은 색으로 칠해진 경우
                    visited[x][y] += dfs(nx, ny);  // 다음 위치 확인 후 칸 수 +
                }
            }
        }

        return visited[x][y];  // 해당 영역에 포함된 칸 수 반환
    }
}