[level2] 프로그래머스 - 카카오프렌즈 컬러링북(JAVA)

만약 예제는 맞는데, 실행하기에서 틀리신다면
원본 picture배열의 값을 바꾸지 마세요!!
=> isVisited활용..ㅠㅠ

 

 

bfs를 이용하여 문제를 풀었다.    => 완탐!!

 

 

1. 이중 for문을 돌면서, 0이 아닌 모든 점에 대해 bfs를 돌린다.

영역 값이 0 이 아니면서, 방문하지 않은 점이면 => bfs를 돌리자!!
     - 현재 자신의 값을 pivot으로 설정
     - 방문처리    => isVisited[r][c] = true
     - queue에 넣어주고 사방 탐색을 한다.
     - 자신의 상하좌우에 위치하면서, 방문하지 않은 점이면서, 자신의 값(pivot)과 같은 값이면
         => queue에 추가, 면적 증가시기기(sum++)
     - queue의 값이 소진 될 때까지, 옆으로 한 칸씩 나아간다.
         => 자신과 같은 값을 가지고, 붙어있는 영역으로 이동하게 된다.
     - 면적을 반환한다.

2. 각 영역 면적의 최댓값을 구한다.    => Math.max()

3. 영역 개수 증가시키기   => numberOfArea++

 

 

🔥  주의 🔥
사실 isVisited를 굳이 만들지 않고, 방문한 점의 picture값을 다시 0으로 만들어서 구해도 되는데,
이 경우 실행하면 틀렸다고 나옵니다 ㅠㅠ
그래서 picture를 복사해서 하시거나, isVisited를 활용하세요 ㅠㅠ

 

 

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

class Solution {
   public static boolean[][] isVisited;

    public static int[] solution(int m, int n, int[][] picture) {
        int numberOfArea = 0;
        int maxSizeOfOneArea = 0;

        isVisited = new boolean[m][n];
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (picture[r][c] != 0 && !isVisited[r][c]) {
                    maxSizeOfOneArea = Math.max(maxSizeOfOneArea, bfs(r, c, m, n, picture));
                    numberOfArea++;
                }
            }
        }

        return new int[] { numberOfArea, maxSizeOfOneArea };
    }

    private static int bfs(int r, int c, int m, int n, int[][] picture) {
        int[] dr = { -1, 1, 0, 0 }, dc = { 0, 0, -1, 1 };	// 상하좌우 이동
        int sum = 1; // 면적(처음 시작점)
        int pivot = picture[r][c]; // 비교할 기준

        Queue<int[]> queue = new LinkedList<int[]>();
        queue.offer(new int[] { r, c });
        isVisited[r][c] = true; // 방문처리

        while (!queue.isEmpty()) {

            int[] p = queue.poll();

            for (int i = 0; i < 4; i++) {
                int nr = p[0] + dr[i];
                int nc = p[1] + dc[i];

                if (nr < 0 || nc < 0 || nr >= m || nc >= n || picture[nr][nc] != pivot || isVisited[nr][nc])
                    continue;

                queue.offer(new int[] { nr, nc });
                isVisited[nr][nc] = true;
                sum++;
            }
        }

        return sum;
    }
}