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

• "영역" —> 상하 좌우로 연결된 같은 색상의 공간.
• 평소 풀던 BFS, DFS 문제와 같다 .
• 구해야 하는 것 : "영역의 개수" , "가장 큰 영역의 넓이는 몇?"
• 풀이법
  • 여기서 "연결된 같은 색상의 공간 " 에서
    • "연결" 범위 : —> 상 하 좌우 . (대각선 포함x)
  • 보통 이런 문제를 푸는 방식
    • 전체 탐색을 하며 , 색이 칠해진 칸을 찾는다.
    • 칠해진 칸을 찾으면 , 그곳부터 BFS를 시행한다.
      • 같은 색으로 칠해졌는지 확인한다.
      • 이미 방문한 칸인지 확인한다.
      • 아직 방문한적 없는 경우, PQ에 넣는다.
      • PQ에서 꺼낼 때 count한다.
    • count개수를 비교하며 max인지 확인한다.

??? 제출하면 실패...

• 질문하기를 살펴봤다.
• 방문한 칸을 picture[y][x] = 0 로 풀이하는 경우 실패하기가 뜬다는 말을 보았다.
• 그래서 어떤 분들은 picture 을 복사해서 따로배열을 만들어서 푼 경우가 있었고
• 나는 visit을 따로 만들어서 풀이했다.

public class Main{
    public static int g_m ,g_n;
    public static int max = 0;
    public static int[][] dirs = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};

    //  m x n 의 2차원 배열 : m 은 row, n은 col
    // 빈 칸은 0 이다.
    public static int[] solution(int m, int n, int[][] picture) {
        max=0;
        int numberOfArea = 0;
        int maxSizeOfOneArea = 0;
        int[] answer = new int[2];
        boolean [][] visit = new boolean[m][n];
        g_m=m;
        g_n=n;
        // 전체 탐색 - Whether current has specific color
        for(int row=0;row<m;row++){
            for(int col=0;col<n;col++){
                if(picture[row][col]>0&&visit[row][col]==false){
                    bfs(row,col,picture,visit);
                    numberOfArea++;
                    //System.out.println(" FIND NEW AREA : "+row+","+col);
                }
            }
        }
        maxSizeOfOneArea =max;
        answer[0] = numberOfArea;
        answer[1] = maxSizeOfOneArea;
        return answer;
    }

    public static void bfs(int y,int x,int[][] picture,boolean[][] visit){
       
        int cnt=0;
        int color = picture[y][x];
        Queue<int[]> pq = new LinkedList<>();
        pq.add(new int[]{y,x});
        visit[y][x] =true;
        while(pq.isEmpty()==false){
            int[] cur = pq.poll();
            cnt++;
            // 방향성
            for(int dir=0;dir<dirs.length;dir++){
                int nextX = cur[1] + dirs[dir][1];
                int nextY = cur[0] + dirs[dir][0];
                if(nextX>=g_n||nextY>=g_m||nextX<0||nextY<0) continue;
                if(picture[nextY][nextX]!=color || visit[nextY][nextX]) continue;
                visit[nextY][nextX] = true;
                pq.add(new int[]{nextY,nextX});
            }
        }
        if(max<cnt) max = cnt;
    }

    public static void Setting() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    }
    public static void main(String[] args) throws IOException{
        //Setting();

        int[] result = 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}});
        //int[] result =solution(3,3, new int[][]{{0, 1, 0}, {1, 1, 0}, {0, 0, 0}});
        //int[] result =solution(3,3, new int[][]{{0, 0, 0}, {0, 0, 0}, {0, 0, 0}});
        System.out.println(result[0]+","+result[1]);
    }
}