프로래머스 Lv2 카카오 프렌즈 컬러링 문제

• 프로래머스 Lv2 카카오 프렌즈 컬러링 문제
  • 해당 문제의 난이도 상승 원인
    • 색깔의 범주 개수를 int의 한계값으로 설정해 압박감
  • 해당 문제를 해결한 방법
    • 재귀함수를 사용해 같은 숫자일 때만 카운팅 하도록 제작
  • 처음 방식에서 변경한 방식
    • 처음
      • n 중 for 문으로 사용하려다가 너무 복잡하고 정확하지 않음
    • 변경
      • DFS (Depth-First Search, 깊이 우선 탐색)와 BFS (Breadth-First Search, 너비 우선 탐색)를 사용한 재귀함수를 작성해 사용하고 이전에 탐색했던 곳은 방문 배열을 생성하여 확인
  • 문제의 핵심
    • 같은 색깔 및 같은 영역에 있는 것들만 카운팅하여 영역과 방문 여부를 체크해 가면서 확인해야함
  • 이 문제의 목적
    • DFS, BFS + 재귀함수를 사용한 방법을 알고 있어야 하며 알고 있어도 직접 사용해서 작성할 수 있어야 하도록 했음
    • DFS (Depth-First Search, 깊이 우선 탐색)와 BFS (Breadth-First Search, 너비 우선 탐색)란 것에 대해 사용법을 익히게 함

package KakaoFriendsColoringBook;

import java.util.Arrays;

class KakaoFriendsColoringBook {
    boolean[][] visited;
    int[] ay = {1, -1, 0, 0}; // 상하
    int[] ax = {0, 0, -1, 1}; // 좌우

    public int searchArea(int cury, int curx, int[][] arr, int y, int x){
        int result = 1;
        visited[cury][curx] = true;

        for(int i = 0; i < 4; i++){
            int ny = cury + ay[i];
            int nx = curx + ax[i];

            if((ny >= 0 && ny < y) && (nx >= 0 && nx < x)){
                if((arr[cury][curx] == arr[ny][nx]) && !visited[ny][nx]){
                    result = result + searchArea(ny, nx, arr, y, x);
                }
            }
        }

        return result;
    }

    public int[] solution(int m, int n, int[][] picture) {
        int[] answer = {0, 0};
        visited = new boolean[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]){
                    int cal = searchArea(i, j, picture, m, n);
                    answer[0] = answer[0] + 1;
                    answer[1] = answer[1] < cal ? cal : answer[1];
                }
            }
        }


        return answer;
    }

    public static void main(String[] args) {
        int m = 6;
        int n = 4;
        int[][] picture = {
                {1, 1, 1, 0},
                {1, 2, 2, 0},
                {1, 0, 0, 1},
                {0, 0, 0, 1},
                {0, 0, 0, 3},
                {0, 0, 0, 3}
        };

        KakaoFriendsColoringBook obj = new KakaoFriendsColoringBook();

        System.out.println("결과 : " + Arrays.toString(obj.solution(m, n, picture)));

    }
}