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

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

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

문제풀이

전형적인 BFS를 응용한 문제였다. 조금 고려해야 되는것은 숫자가 다르다면 영역이 다르다는 것과

상하좌우로 연결이 안되어 있으면 영역이 나뉜다는 것이다.

그래서 2중 반복문으로 전체적으로 돌면서 "0"이 아닌 구역이나 이미 방문한 구역이면 지나가고

아직 방문하지 않았다면 bfs로 체크해주면서 방문체크를 해줘었다.

bfs에 들어갈때마다 구역을 설정하기 때문에 numberOfArea를 증가시켜 주었고,

Queue에 들어갈때마다 영역의 수가 증가 하기때문에 갯수를 체크해줘서

가장 큰 값을 maxSizeOfOneArea로 설정해주었다.

 

코드

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    static boolean[][] visited;
    static int maxSize;
    static int[] dx = {0,0,1,-1};
    static int[] dy = {1,-1,0,0};
    
    public int[] solution(int m, int n, int[][] picture) {
        visited = new boolean[m][n];
        maxSize =0;
        int numberOfArea = 0;
        int maxSizeOfOneArea = 0;
        
        for(int i =0; i<m; i++){
            for(int j =0; j<n; j++){
                if(picture[i][j] ==0 || visited[i][j]) continue;
                bfs(i,j,picture[i][j],m,n,picture);
                numberOfArea++;
                maxSizeOfOneArea = Math.max(maxSizeOfOneArea, maxSize);
            }
        }
        int[] answer = new int[2];
        answer[0] = numberOfArea;
        answer[1] = maxSizeOfOneArea;
        return answer;
    }
    
    public void bfs(int x, int y, int pix ,int m, int n, int[][] picture){
        Queue<Pos> qu = new LinkedList<>();
        qu.add(new Pos(x,y));
        visited[x][y] = true;
        int index =0;
        
        while(!qu.isEmpty()){
            int size = qu.size();
            index += size;
            for(int i=0; i<size; i++){
                Pos pos = qu.poll();
                for(int k =0; k<4; k++){
                    int a = pos.x +dx[k];
                    int b = pos.y +dy[k];
                    
                    if(a<0 || a>=m || b<0 || b>=n || picture[a][b] != pix || visited[a][b] == true) continue;
                    
                    qu.add(new Pos(a,b));
                    visited[a][b] = true;
                }
            }
        }
        
        maxSize = index;
    }
    
    static class Pos{
        int x;
        int y;
        public Pos(int x, int y){
            this.x =x;
            this.y =y;
        }
    }
}