[프로그래머스/1829] 카카오프랜즈 컬러링북 (Java)

Question

• 문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/1829
• 분류 : BFS
• 풀이 시간 : 15분

문제 해설

1. 그림을 나타내는 m × n 크기의 2차원 배열 한 칸(=영역)에는 0 이상 2^31 - 1 이하의 임의의 값이 들어있음
   1. 0 = 색칠하지 않은 영역
2. 배열에서 색칠된 영역의 개수와 가장 큰 영역의 넓이를 구하여라

Solution

풀이 접근 방법

1. 영역 = 서로 같은 값을 가지고, 상하좌우로 연결되어있어야 함
2. 가장 큰 영역의 넓이 구하기
   1. 자신의 영역과 같은 값을 가진 상하좌우 연결된 영역으로 이동하면서 탐색 = BFS

정답 코드

import java.util.*;

class Solution {
    class Node {
        int x, y;
        
        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    
    int M, N;
    
    public int[] solution(int m, int n, int[][] picture) {
        int[] answer = new int[2];
        boolean[][] visited = new boolean[m][n];
        
        M = m;
        N = n;
        
        int countArea = 0;
        int maxArea = Integer.MIN_VALUE;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
              	// 색칠해있는 영역 + 영역 탐색하지 않은 곳이면 탐색
                if (picture[i][j] != 0 && !visited[i][j]) {
                  	// 해당 값을 가진 영역을 탐색 -> 영역의 크기 리턴
                    int area = checkArea(i, j, visited, picture);
                    
                    countArea++;
                    maxArea = Math.max(maxArea, area);
                }
            }
        }
        return new int[]{countArea, maxArea};
    }
    
    int checkArea(int x, int y, boolean[][] visited, int[][] picture) {
        int[] dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};
        int area = 1;
        int value = picture[x][y];
        Queue<Node> queue = new LinkedList<Node>();
        
        queue.add(new Node(x, y));
        visited[x][y] = true;
        
        while(!queue.isEmpty()) {
            Node node = queue.poll();
            
            for(int i = 0; i < 4; i++) {
              	// 상하좌우로 연결된 영역 탐색
                int nx = node.x + dx[i];
                int ny = node.y + dy[i];
                
              	// 범위 밖을 벗어나거나
                // 이미 방문한 영역이거나
                // 탐색하려는 영역의 값과 다른 경우 탐색하지 않음
                if (!isIn(nx, ny) || visited[nx][ny] || picture[nx][ny] != value)
                    continue;
                
                visited[nx][ny] = true;
                queue.add(new Node(nx, ny));
                area++;
            }
        }
        
        return area;
    }
    
    boolean isIn(int x, int y) {
        if (0 <= x && x < M && 0 <= y && y < N)
            return true;
        return false;
    }
}