[프로그래머스]카카오예선_BFS

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

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

 

영역의 갯수 구하기 + 영역의 넓이 구하기 문제

 

import java.util.LinkedList;
import java.util.Queue;
import java.awt.Point;
 
class Solution {
    int []dx = {-1,1,0,0};
    int []dy = {0,0,-1,1};
    
    public int[] solution(int m, int n, int[][] picture) {
        int numberOfArea = 0;
        int maxSizeOfOneArea = 0;
        boolean [][]isV = new boolean[m][n];
        Queue<Point> q = new LinkedList<>();
        
        for(int y=0;y<m;y++){
            for(int x=0;x<n;x++){
                if(picture[y][x] != 0 && !isV[y][x]){
                    //0이 아니면 BFS 시작
                    int value = picture[y][x];
                    int cnt = 1; //넓이
                    isV[y][x] = true;
                    numberOfArea++; //영역 갯수
                    q.add(new Point(x,y));
                    
                    while(!q.isEmpty()){
                        Point p = q.poll();
                        int tmpX = p.x;
                        int tmpY = p.y;
                        
                        for(int i=0;i<4;i++){
                            int nx = tmpX + dx[i];
                            int ny = tmpY + dy[i];
                            
                            if(nx <0 || nx >= n || ny <0 || ny >= m || isV[ny][nx] || picture[ny][nx] != value) continue;
                            q.add(new Point(nx,ny));
                            isV[ny][nx]=true;
                            cnt++;
                        }
                    }
                    maxSizeOfOneArea = cnt >= maxSizeOfOneArea ? cnt : maxSizeOfOneArea;
                }
            }
        }
        int[] answer = new int[2];
        answer[0] = numberOfArea;
        answer[1] = maxSizeOfOneArea;
        return answer;
    }
}