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

문제

https://www.acmicpc.net/problem/1829

풀이

• 기본적인 BFS 문제
• 상하좌우를 탐색하되 색이 다르거나, 범위를 벗어났을 때를 제외해주면 쉽게 구할 수 있다.
• picuture배열을 돌면서 처음 visit하지 않은 곳을 찾았을 때 새로운 색깔 영역이 되고, 그 안에서 탐색을 몇번 하는가가 해당 색깔의 넓이가 된다.

유의할 점

코드

import java.util.*; 
class Solution {
    static int[] dx= {1,0,-1,0};
    static int[] dy = {0,1,0,-1}; 
    static boolean[][] visited ;
    public int[] solution(int m, int n, int[][] picture) {
        Queue<int[]> q = new LinkedList<>(); 
        visited =new boolean[m][n]; 
        int numberOfArea =0; 
        int max =0; 
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(!visited[i][j] && picture[i][j]!=0){
                    numberOfArea++; 
                    int maxSizeOfOneArea =0; 
                    q.add(new int[]{i,j});
                    while(!q.isEmpty()){
                        int[]curr = q.poll(); 
                        for(int dir=0; dir<4; dir++){
                            int nx = curr[0]+dx[dir]; 
                            int ny = curr[1]+dy[dir]; 
                            if(nx<0||ny<0||nx>=m||ny>=n) continue; 
                            if(visited[nx][ny]||picture[nx][ny]==0 || picture[nx][ny]!= picture[curr[0]][curr[1]]) continue; 
                            q.add(new int[]{nx,ny});
                            maxSizeOfOneArea++; 
                            visited[nx][ny] = true; 
                        } 
                    }
                    max = Math.max(max,maxSizeOfOneArea );
                }
            }
        }
    
        return new int[]{numberOfArea,max};
    }
}