[Programmers] 카카오프렌즈 컬러링북

[Level 2] 카카오프렌즈 컬러링북

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

• 그림에 몇 개의 영역이 있는지와 가장 큰 영역의 넓이는 얼마인지 계산하는 프로그램 작성
• 영역이란 상하좌우로 연결된 같은 색상의 공간을 의미한다.
• 그림의 원소 중 값이 0인 경우는 색칠하지 않는 영역을 뜻한다.

 

 

Solution

• picture 전체 배열을 돌면서 0이 아니면서 아직 방문하지 않은 영역(count 하지 않은 영역)에 대해 BFS를 돌린다.
• BFS()에서는 해당 영역에 해당하는 최대 칸 수를 갱신하고 max 변수에 저장한다. 

 

 

소스코드

 

import java.util.*;
 
class Solution {
    static int[][] visited, map;
    static int dx[] = {1,-1,0,0};
    static int dy[] = {0,0,1,-1};
    static int max, r, c;
    static Queue<Dot> q;
    
    static class Dot{
        private int x,y;
        public Dot(int x, int y){
        this.x = x;
        this.y = y;
        }
    }   
     public int[] solution(int m, int n, int[][] picture) {
        int numberOfArea = 0;
        int maxSizeOfOneArea = 0;
        int[] answer = new int[2];
        
        init(m,n,picture);
    
         for(int i = 0; i<m; i++){
             for(int j = 0; j<n; j++){
                 if(map[i][j] > 0 && visited[i][j] == 0){
                     bfs(new Dot(i,j), map[i][j]);
                     numberOfArea++;
                 }
             }
         }
        
        answer[0] = numberOfArea;
        answer[1] = max;
        return answer;
    }
        
    static void bfs(Dot dot, int color){
         int count = 0;
        q = new LinkedList<>();
        q.offer(dot);
        visited[dot.x][dot.y] = 1;
        
        while(!q.isEmpty()){
            count++;
            Dot cur = q.poll();
            
            int nx,ny;
            for(int i = 0; i<4; i++){
                nx = dx[i] + cur.x;
                ny = dy[i] + cur.y;
                
                if(nx >= r || ny >= c || nx < 0 || ny <0)
                    continue;
                
                if(map[nx][ny] != color || visited[nx][ny] == 1)
                    continue;
                
                q.offer(new Dot(nx,ny));
                visited[nx][ny] = 1;
            }
        }
        max = Math.max(max,count);
    }
        
    static void init(int m, int n, int[][] arr){
        r = m;
        c = n;
        max = Integer.MIN_VALUE;
        map = new int[r][c];
        visited = new int[r][c];
        
        for(int i = 0; i<r; i++){
            map[i] = arr[i].clone();
        }
    }
}