문제

[프로그래머스] 카카오프렌즈 컬러링북
https://school.programmers.co.kr/learn/courses/30/lessons/1829

풀이

조건

• 몇 개의 영역이 있는지와 가장 큰 영역의 넓이는 얼마인지 계산한다.
• 영역이란 상하좌우로 연결된 같은 색상의 공간을 의미한다.
• picture의 원소 중 값이 0인 경우는 색칠하지 않는 영역을 뜻한다.

풀이 순서

• BFS를 사용한다.
• 모든 좌표를 탐색하며 영역 수와 영역 크기를 구한다.
  • 아직 체크하지 않았고 색칠이 되어 있는 영역이면 BFS를 시작한다.
  • 해당 색인 영역의 크기를 구한다.

코드

Java

import java.util.*;

class Solution {
    
    // 방문 체크할 배열
    static boolean[][] isVisited;
    // 우, 좌, 하, 상 방향 나타내는 배열
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    // picture의 세로, 가로 길이
    static int R, C;
    
    public int[] solution(int m, int n, int[][] picture) {
        int numberOfArea = 0;
        int maxSizeOfOneArea = 0;
        // picture의 세로, 가로 길이
        R = m;
        C = n;
        
        // 모든 좌표를 탐색하며 영역 수와 영역 크기 구함
        isVisited = new boolean[m][n];
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
            	// 아직 체크 X && 색칠 O
                if(!isVisited[i][j] && picture[i][j] != 0) {
                	// BFS를 사용해 영역 크기 구함
                    int rst = bfs(i, j, picture[i][j], picture);
                    // 영역 수
                    numberOfArea++;
                    // 영역 크기 중 최대값 저장
                    maxSizeOfOneArea = Math.max(maxSizeOfOneArea, rst);
                }
            }
        }        

        int[] answer = new int[2];
        answer[0] = numberOfArea;
        answer[1] = maxSizeOfOneArea;
        return answer;
    }
    
    // BFS 사용
    static int bfs(int r, int c, int color,int[][] picture) {
        int total = 1; // 현재 색의 영역 크기 저장할 변수
        
        Queue<int[]> que = new LinkedList<>();
        
        // 시작 좌표 큐에 넣고 방문 체크
        que.add(new int[]{r, c});
        isVisited[r][c] = true;
        
        while(!que.isEmpty()) {
            int[] now = que.poll();
            
            int x = now[0];
            int y = now[1];
            
            for(int t = 0; t < 4; t++) {
                int nx = x + dx[t];
                int ny = y + dy[t];
                // 범위 체크
                if(nx < 0 || ny < 0 || nx >= R || ny >= C) continue;
                // 방문 체크
                if(isVisited[nx][ny]) continue;
                // 색깔 체크
                if(picture[nx][ny] == color) {
                    total++;
                    isVisited[nx][ny] = true;
                    que.add(new int[]{nx, ny});
                }
            }
        }
        
        return total;
    }
}

정리

• 전형적인 BFS 문제였다.