https://programmers.co.kr/learn/courses/30/lessons/1829
https://github.com/parkjbdev/AlgoStudy/tree/main/programmers/카카오프렌즈%20컬러링북

소스코드

class Prob1829 {
  private final int m, n;
  private final int[][] picture;
  private boolean[][] isVisit;

  public Prob1829(int m, int n, int[][] picture) {
    this.m = m;
    this.n = n;
    this.picture = picture;
    isVisit = new boolean[m][n];
  }

  public int[] solve() {
    int numberOfArea = 0;
    int maxSizeOfOneArea = 0;

    for (int i = 0; i < m; i++)
      for (int j = 0; j < n; j++)
        if (picture[i][j] != 0 && !isVisit[i][j]) {
          numberOfArea++;
          int count = countArea(i, j, picture[i][j]);
          if (count > maxSizeOfOneArea)  maxSizeOfOneArea = count;
        }

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

  private boolean isRange(int m, int n) {
    return 0 <= m && m < this.m && 0 <= n && n < this.n;
  }

  private int countArea(int m, int n, int num) {
    if (!isRange(m, n))  return 0;
    if (picture[m][n] != num)  return 0;
    if (isVisit[m][n])  return 0;
    isVisit[m][n] = true;
    return 1 + countArea(m + 1, n, picture[m][n]) + countArea(m, n + 1, picture[m][n])
        + countArea(m - 1, n, picture[m][n]) + countArea(m, n - 1, picture[m][n]);
  }
}

풀이

이중 for 루프로 각 좌표들을 순회하면서, 좌표에 해당하는 번호가 0이 아닌, 방문하지 않은 좌표인 경우, 해당 좌표가 포함된 구간을 방문하지 않은 것으로 판단하여 numberOfArea를 1 증가시켜 주었다. 그리고 해당 영역의 구간넓이를 countArea로 구한 뒤, 최대 구간넓이 maxSizeOfOneArea 를 갱신시켜준다.

구간넓이 계산

DFS를 이용하여 각 영역을 탐색하면서 해당 영역의 넓이를 구해주었다.
countArea(시작좌표 x, 시작좌표 y, 시작하는 칸의 번호) 함수에서

• 좌표가 범위안에 들지 않는 경우
• (좌표에 해당하는 번호) != (이전 좌표칸의 번호) 의 경우
• 이미 방문했던 좌표일 경우

에 0을 반환하도록 하였고, 그렇지 않은 경우 정상적인 방문을 하여 반환값으로 1과 다음 상하좌우의 좌표들에 방문한 값들을 더해 주었다.