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

문제

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

프로그래머스

 

---

 

문제 설명

카카오 프렌즈 컬러링북 문제는 2차원 배열로 주어진 그림에서 서로 연결된 같은 색상 영역의 개수와 가장 큰 영역의 넓이를 계산하는 문제입니다. 영역이란 상하좌우로 연결된 같은 색상의 공간을 의미합니다. 배열의 값이 0이면 색칠하지 않는 공간을 나타내며, 이 공간은 영역의 일부로 간주되지 않습니다.

목표는 입력으로 주어지는 그림을 분석하여 총 몇 개의 색상 영역이 있는지, 그리고 가장 큰 영역의 넓이가 몇 칸인지 반환하는 것입니다.

접근 방법

1. 탐색 알고리즘:
   • 그림을 탐색하기 위해 BFS(너비 우선 탐색)나 DFS(깊이 우선 탐색) 알고리즘을 사용합니다. 이 알고리즘은 현재 위치에서 시작하여 상하좌우 인접한 같은 색상의 칸들을 탐색하고 연결된 영역을 구하는 데 사용됩니다.
2. 방문 체크:
   • visited 배열을 사용하여 각 위치의 방문 여부를 기록합니다. 이미 방문한 위치는 탐색하지 않도록 합니다.
3. 영역 탐색:
   • 그림의 각 위치를 순차적으로 확인하며, 아직 방문하지 않았고 0이 아닌 색상인 경우 BFS나 DFS를 시작합니다.
   • 탐색을 통해 하나의 영역을 확인할 때마다 영역의 크기를 계산하고, 최대 크기를 기록합니다.

 

import java.util.*;
class Solution {
    static int[] dy = {-1,1,0,0};
    static int[] dx = {0,0,-1,1};
    static boolean[][] visited;
    static int maxVal;
    public static void bfs(int y, int x, int m, int n, int color, int[][] picture) {
        int tmp = 0;
        Queue<int[]> queue = new ArrayDeque<>();
        queue.add(new int[] {y,x});
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!queue.isEmpty()) {
                    int yy = queue.peek()[0];
                    int xx = queue.peek()[1];
                    queue.poll();
                    for (int d = 0; d < 4; d++) {
                        int ny = yy + dy[d];
                        int nx = xx + dx[d];
                        if (0 <= ny && ny < m && 0 <= nx && nx < n && !visited[ny][nx] && picture[ny][nx] == color) {
                            visited[ny][nx] = true;
                            queue.add(new int[] {ny,nx});
                            tmp++;
                        }
                    }
                }
            }
        }
        if (maxVal < tmp) maxVal = tmp;
    }
    public int[] solution(int m, int n, int[][] picture) {
        maxVal = 0;
        int[] result = new int[2];
        int cnt = 0;
        visited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!visited[i][j] && picture[i][j] != 0) {
                    bfs(i,j,m,n,picture[i][j],picture);
                    cnt++;
                }
            }
        }
        result[0] = cnt;
        result[1] = maxVal;
        return result;
    }

}