[프로그래머스,자바] Level2: 카카오프렌즈 컬러링북

 

문제분석:

 

요구사항:  1. 영역은 몇개인가?   2. 영역중에서 가장 많은넓이를 차지하는값은 무엇인가?

 

보는바와 같이, 완전탐색을 행해야한다.  모든 영역을 탐색한뒤에 영역을 나누고, 영역의 넓이를 더해야한다.

 

완전탐색을 쓰기전에  DFS, BFS 둘중 하나를 골라야한다. 필자는 여기서 DFS를골랐다.

 

DFS는 재귀 , 스택을 사용하니 비교적 깔끔한 코드가 나온다.

 

먼저 DFS를 쓰기위한 재료? 들을 준비해야한다.

뒤에서 쓸 재귀함수의 파라미터를 깔끔하게 하기위해서 

필요한 재료들은 미리 전역변수로 올려놨다.

 

v 와 h는  너비와 높이제한을 위해서,

visited는 이미 체크가 완료된 블록을 중복체크를 방지하기위해서

target은  같은영역만을 체크하기위한 기준을 잡기위해

board는  picture과 동일한기능이지만 전역으로 빼내기위해

total은  하나의 영역이 끝나면 갯수를 저장하기 위해서 선언을했습니다.

 

 

이 부분에서의 재귀함수는 바로 search(i,j) 부분이다.

 

이 로직은 모든 블록을탐색하여, 체크하지않은부분을  search()함수로 영역의 넓이를 세준다.

 

그렇게 세준 영역은,  리스트에 {영역의색깔 , 영역의 넓이} 형태로 저장한다.

 

 

 

재귀함수 영역이다. 

 

search 함수는  상 하 좌 우 4방향으로 탐색을하는데, 2가지 경우를 제외해야한다.

 

1. 벽에 부딪혓을때:  보드 밖으로 나가는경우는 제외해줘야한다.

 

2. 다른색과 만났을때 : 다른색과 만나면 다른 영역이므로 이 경우도 탐색을 그만둬야한다.

 

앞에서 필요한 재료들을 전역변수로 다 옮겨놨기때문에 비교적 search함수의 파라미터가 깔끔하다.

 

 

마지막으로 결과를 정리하는일만 남았다.

 

영역의 갯수는 리스트의 저장된 갯수와 동일하고

 

영역이 제일 큰 넓이는 리스트의 저장된 '영역의 넓이' 기준으로 내림차순 정렬을 해주고

제일 높은값 (첫번째)을 반환한다.

 

문제풀이

import java.util.*;
class Solution {
int v=0;
int h=0;
boolean[][] visited;  
int target=0;
int[][] board;
int total=0;
    public int[] solution(int m, int n, int[][] picture) {
        int numberOfArea = 0;
        int maxSizeOfOneArea = 0;       
        v=m;
        h=n;
        board=picture;
        
        List<int[]> list = new ArrayList<>();       
        visited = new boolean[m][n];                   
            for(int i=0;i<m;i++){
                for(int j=0;j<n;j++){
                    if(visited[i][j]==false){
                        target=picture[i][j];
                        if(target==0){
                            continue;
                        }
                        total=0;
                        search(i,j);
                        list.add(new int[]{target,total});
                    }
                }
            }
        numberOfArea=list.size();
        Collections.sort(list,(a,b)->(b[1]-a[1]));
        maxSizeOfOneArea=list.get(0)[1];
        
        int[] answer = new int[2];
        answer[0] = numberOfArea;
        answer[1] = maxSizeOfOneArea;
        return answer;
    }
    
    public void search(int m,int n){
       //벽에 부딪혓을때
       if(m<0||m==v||n<0||n==h){
           return;
       } 
       //다른색과 만났을때
       if(board[m][n]!=target){       
           return;
       }       
        //4방향 탐색
       if(visited[m][n]==false){
        visited[m][n]=true;   
        total++;
        search(m-1,n);
        search(m,n-1);
        search(m+1,n);
        search(m,n+1);
       }    
    }
}