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

코딩 테스트 풀이 체크리스트
2시간 내에 풀었는가?	O
본인의 실력으로 풀었는가?	O

 

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

 

 

 

 

 

class Solution {
    
    int numberOfArea, maxSizeOfOneArea;    
    boolean[][] check;
    
    public int[] solution(int m, int n, int[][] picture) {
        numberOfArea = 0;
        maxSizeOfOneArea = 0;
        
        check = new boolean[m][n];
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (picture[i][j] == 0 || check[i][j]) continue;
                
                int num = func(picture, i, j);
                
                numberOfArea++;
                maxSizeOfOneArea = Math.max(maxSizeOfOneArea, num);
            }
        }
        
        return new int[]{numberOfArea, maxSizeOfOneArea};
    }
    
    public int func(int[][] picture, int x, int y) {
        int[] xMove = {0, 0, 1, -1};
        int[] yMove = {1, -1, 0, 0};
        
        int result = 1;
        
        if (check[x][y]) return 0;
        
        check[x][y] = true;
        
        for (int i = 0; i < 4; i++) {
            if (x + xMove[i] < 0 || y + yMove[i] < 0) continue;
            if (x + xMove[i] >= picture.length  || y + yMove[i] >= picture[x].length) continue;
            if (picture[x][y] != picture[x+xMove[i]][y+yMove[i]]) continue;

            result += func(picture, x+xMove[i], y+yMove[i]);
        }
        
        return result;
    }
}

 

테스트 1 〉

통과 (24.20ms, 92.6MB)

 

 

 

 

 

너비 우선 탐색 (BFS)

이중 for문으로 picture와 방문했는지 확인하기 위해서 만든 check를 순차적으로 확인하는데, 방문을 했는지 안했는지 체크하고 방문 안했으면 func함수를 돌린다.

 

 

 

 

func함수에서는 상하좌우 칸이 같은 숫자면 func함수에 넣어 또 함수를 돌리고.. 재귀함수같이..?

그렇게 해서 칸의 개수를 가져옴.

어차피 상하좌우 방문 안해도 자기 숫자 하나는 가져올 수 있도록 했고, 방문한 칸이면 0으로 리턴하게 만들어서 두 번 방문할 일은 없을 것이다.

 

 

 

 

예전엔 정말 어려워서 몇 시간동안 끙끙 잡고 있었는데 그래도 어떻게 푸는지 알고 있으니까 쉽게 접근할 수 있었음.

 

 

 

 

 

 

 

왜 이렇게 만들었나 싶을 정도로 이해할 수 없는 코드...

과거의 나 왜 그랬어?

 

 

 

import java.util.*;

class Solution {
    public int[] solution(int m, int n, int[][] picture) {
        int numberOfArea = 0;
        int maxSizeOfOneArea = 0;

        int[][] pic = new int[picture.length][picture[0].length];
        int[][] temp = new int[pic.length][pic[0].length];
        
        for(int i = 0; i < pic.length; i++){
            for (int j = 0; j < pic[0].length; j++){
                pic[i][j] = picture[i][j];
            }
        }
        
        for (int i = 0; i < pic.length; i++){
            for (int j = 0; j < pic[0].length; j++){
                int ans = funk(pic, temp, i, j);
                
                if (ans != 0){
                    numberOfArea++;
                    maxSizeOfOneArea = Math.max(maxSizeOfOneArea, ans);
                }
            }
        }
        
        int[] answer = new int[2];
        answer[0] = numberOfArea;
        answer[1] = maxSizeOfOneArea;
        return answer;
    }
    
    public int funk(int[][] pic, int[][] temp, int i, int j){
        if (pic[i][j] == 0) return 0;
        
        if (temp[i][j]++ > 0) return 0;
        
        int ans = 1;
        
        if (i+1 != pic.length) {
            if (pic[i+1][j] == pic[i][j]){
                ans += funk(pic, temp, i+1, j);
            }
        }
        
        if (j+1 != pic[0].length){
            if (pic[i][j+1] == pic[i][j]){
                ans += funk(pic, temp, i, j+1);
            }
        }        
            
        if (i-1 >= 0){
            if (pic[i-1][j] == pic[i][j]){
                ans += funk(pic, temp, i-1, j);
            }
        }
        
        if (j-1 >= 0) {
            if (pic[i][j-1] == pic[i][j]){
                ans += funk(pic, temp, i, j-1);
            }
        }
        
        return ans;
    }
}