プログラマー-ココアカラーブック

要求

Kakaofriendsの友達がカラーブックを作る時、分野が多ければ多いほど難易度が高くなります.とにかくその方法で分野を探す(=>典型的なBFS問題)
だから、分野の中で最大の分野の大きさと、カラーベルの本の中にいくつかの分野があることを教えてください.

キーワード

BFSとマッピングの問題を巡るキーワードは

        static boolean[][] visit;
        static int[] xMap = {-1,1,0,0};
        static int[] yMap = {0,0,1,-1};

以上の3つがポイントです.visitは、dx/dyが(上、下、左、右)移動可能な座標であるノードにアクセスしたかどうかを示します.
そこで,BFSに入力された値に基づいて,アクセスを上下左右に移動する際にtrueタグを行い,同じ領域であるかどうかを探索することを目標とする.
このコードは以下の通りです.

package Programmers;

import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

public class 카카오컬러링북 {

    public static void main(String[] args) {
        Solution solution = new Solution();
        final int[] solution1 = solution.solution(6, 4, new int[][]{{1, 1, 1, 0}, {1, 2, 2, 0}, {1, 0, 0, 1}, {0, 0, 0, 1}, {0, 0, 0, 3}, {0, 0, 0, 3}});
        System.out.println(Arrays.toString(solution1));
    }

    static class Solution {
        static boolean[][] visit;
        static int[] xMap = {-1,1,0,0};
        static int[] yMap = {0,0,1,-1};

        public int[] solution(int m, int n, int[][] picture) {
            int[] answer = new int[2];
            visit = new boolean[m][n];

            for(int i = 0; i < m; i++){
                for(int j = 0; j < n; j++){
                    if(visit[i][j] || picture[i][j] == 0){
                        continue;
                    }
                    answer[1] = Math.max(answer[1], bfs(picture, i, j));
                    answer[0]++;
                }
            }
            return answer;
        }

        int bfs(int[][] picture, int x, int y){
            Queue<int[]> queue = new LinkedList<>();
            int area = 1, dx, dy;
            visit[x][y] = true;
            queue.offer(new int[]{x,y});

            while (!queue.isEmpty()){
                int[] poll = queue.poll();

                for(int i = 0; i < 4; i++){
                    dx = poll[0] + xMap[i];
                    dy = poll[1] + yMap[i];

                    if(dx >= 0 && dy >= 0 && dx < picture.length && dy < picture[0].length){
                        if(!visit[dx][dy] && picture[dx][dy] != 0 && picture[poll[0]][poll[1]] == picture[dx][dy]){
                            visit[dx][dy] = true;
                            queue.offer(new int[]{dx, dy});
                            area++;
                        }
                    }
                }
            }
            return area;
        }
    }
}

BFS

BFSはブラウズノード毎であり,この問題を解く際にDFSよりも速い.したがって,X|Yでナビゲートし,領域を探し続け,異なる場合は領域を追加しない.ナビゲーションが完了したらareaに戻ります.だから同じ数字の時に回り続けます.BFSは通常スタックを使用する.BFS/DFSの概念を正確に把握するには,プログラマというより,BFSとDFSが理解されるまで標準アルゴリズムの段階的な解答にある.いずれにしても、プログラマーはこれが良い概念ではないと思っています.

書く理由

アルゴリズムを書かなくても、考えが整理されているようなので、あまり書かないのが普通ですが...最近ずっと問題を解いていますが、こんな簡単な問題で足を引っ張られるとは思いませんでした.本当に時間がかかってしまったので整理に使いました
土曜日はcoteで大変なことになりました~~!こんな質問に足を引っ張られたら、答えもない.