[Java]Programmers Carcao friendsカラー絵本

16407 ワード
BFS programmers algorithm テキストリンク

Programmers Carcao friendsカラー絵本

  • BFS
  • 72017 KACO CODE予選

    • 🔍 問題の説明


    https://programmers.co.kr/learn/courses/30/lessons/1829#
    ココア友彩本
    出版社の編集者オフィチトニオは、絵本に描かれた円を何枚も描いた.複数の画像を難易度順にカラー絵本に入れたい魚は、領域が多ければ塗りにくくなることを発見し、画像の難易度を領域数と定義した.(領域とは上下左右に接続された同じ色の空間を指す.)
    図にどれだけの領域があるか、最大の領域の幅がどれだけあるかを計算するプログラムを作成します.

    上図には12の領域があり、最も広い領域は魚の皮魚の顔で、幅は120です.

    ✔入力形式


    画像サイズを表すmとn、および画像を表すmを入力する× nサイズの2次元配列図を与えます.制限条件は以下の通りです.
    1 <= m, n <= 100
    pictureの要素は0以上2^31-1以下の任意の値である.
    pictureの要素の値が0の場合は着色しない領域を表す.

    ✔出力フォーマット


    戻りタイプは、2つの要素の整数配列です.図の領域の数と最大の領域の数を返します.

    💡 に答える


    BFSとAccessで各領域の数を調べた

    💬 ソースコード

    import java.util.*;

class Solution {
    static boolean[][] visited;
    static int maxSizeOfOneArea, M, N;
    static int[] dr = {-1,1,0,0};
    static int[] dc = {0,0,-1,1};
    
    public int[] solution(int m, int n, int[][] picture) {
        int numberOfArea = 0;
        maxSizeOfOneArea = 0;
        M = m;
        N = n;
            
        visited = new boolean[m][n];
        
        for(int i = 0; i < m; i ++){
            for(int j = 0 ; j < n ; j++){
                if(visited[i][j]) continue;
                if(picture[i][j]==0) continue;
                bfs(i,j,picture);
                numberOfArea++;
            }
        }
            

        int[] answer = new int[2];
        answer[0] = numberOfArea;
        answer[1] = maxSizeOfOneArea;
        return answer;
    }
    
    static void bfs(int x, int y, int[][] picture){
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{x,y});
        visited[x][y] = true;
        
        int color = picture[x][y];
        int cnt = 1;
        
        while(!queue.isEmpty()){
            int[] cur = queue.poll();
            int r = cur[0];
            int c = cur[1];
            
            for(int d = 0 ; d < 4 ; d++){
                int nr = r + dr[d];
                int nc = c + dc[d];
                if(isIn(nr,nc)&&!visited[nr][nc]&&
                   color==picture[nr][nc]){
                    cnt++;
                    visited[nr][nc] = true;
                    queue.add(new int[]{nr,nc});
                }
            }
        }
        
        maxSizeOfOneArea = Math.max(cnt, maxSizeOfOneArea);
    }
    
    static boolean isIn(int r, int c){
        if(r<0||c<0||r>=M||c>=N) return false;
        return true;
    }
}
    Bootstrap進捗バー
    [アルゴリズム]平方ソート