문제

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

---

입력

• 그림의 크기를 나타내는 m과 n
• 그림을 나타내는 m × n 크기의 2차원 배열 picture

---

출력

그림에 몇 개의 영역이 있는지와 가장 큰 영역은 몇 칸으로 이루어져 있는지를 리턴

---

풀이

제한조건

• 1 <= m, n <= 100
• picture의 원소는 0 이상 2^31 - 1 이하의 임의의 값이다.
• picture의 원소 중 값이 0인 경우는 색칠하지 않는 영역을 뜻한다.

접근방법

탐색

BFS 또는 DFS를 통해 영역을 찾고, 영역의 크기를 찾는 문제이다.

1. 탐색의 시작점 찾기
2. 탐색하며 영역의 크기 구하기.
3. 영역의 크기 저장하기.

1. 탐색의 시작점 찾기
탐색한 적이 없으며, 색칠할 필요가 없는 곳을 제외한 나머지 영역에 대해서 모두 탐색해야한다.
입력으로 주어진 picture의 모든 지점에 대해 조건을 검사하고, 해당 지점에서부터 탐색을 이어나가자.

2. 탐색하며 영역의 크기 구하기.
DFS 또는 BFS를 이용하여 영역의 크기를 구하면된다.
BFS를 이용하여 Queue에 새로운 지점이 추가될 때마다 count 변수의 값을 증가시켜 주는방식으로
구현했다. (DFS를 이용하여 재귀적으로 수행하는것이 조금 더 번거롭다)

3. 영역의 크기 저장하기.
2번에서 구한 영역의 크기를 List에 담아둔다.
문제에서 어떤영역의 크기가 가장 큰 것인지를 요구하는것이 아니기때문에 단순 크기만 담아도 상관없다.

이제 List의 크기가 전체 영역의 수이고, List에서 최대값이 가장 큰 영역의 크기이다.

---

코드

import java.util.*;

class Solution {
    static boolean[][] visit;
    static int[][] map;
    static List<Integer> list;
    static int N, M;
    public int[] solution(int m, int n, int[][] picture) {
        N = n;
        M = m;
        map = picture;
        list = new ArrayList();
        visit = new boolean[m][n];
        
        for(int i = 0 ; i < m; ++i){
            for(int j = 0 ; j < n; ++j){
                if(!visit[i][j] && map[i][j] != 0){
                    search(i,j);
                }
            }
        }
        
        int[] answer = new int[2];
        answer[0] = list.size();
        answer[1] = list.stream().max(Integer::compare).get();
        
        return answer;
    }
    
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    
    public void search(int startX, int startY){
        int count = 1;
        visit[startX][startY] = true;
        Queue<int[]> q = new ArrayDeque();
        q.add(new int[] {startX, startY});
        while(!q.isEmpty()){
            int[] cur = q.poll();
            for(int d = 0; d < 4; ++d){
                int nextX = cur[0] + dx[d];
                int nextY = cur[1] + dy[d];
                if(0 <= nextX && nextX < M && 0 <= nextY && nextY < N){
                    if(!visit[nextX][nextY] && map[nextX][nextY] == map[startX][startY]){
                        visit[nextX][nextY] = true;
                        q.add(new int[] {nextX, nextY});
                        count++;
                    }
                }
            }   
        }
        list.add(count);
    }
}