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

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

 

소요시간 : 18분

 

그냥 dfs로 blob 구하는 문제. 매우 쉬웠음

방문하지 않았고 0이 아닌 값을 찾으면 dfs 실행해서 주변 연결된 것들 다 찾고 cnt 와 MAX 값 비교해서 갱신한다.

class Solution {
  public int[] solution(int m, int n, int[][] picture) {
    M = m;
    N = n;
    int numberOfArea = 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) {
          numberOfArea++;
          cnt = 1;
          visited[i][j] = true;
          dfs(i, j, picture);
          if(MAX < cnt) MAX = cnt;
        }
      }
    }

    int[] answer = new int[2];
    answer[0] = numberOfArea;
    answer[1] = MAX;
    return answer;
  }

  boolean[][] visited;
  int MAX = 0, M, N, cnt;
  int[][] dir = { {-1, 0},{0, 1},{1, 0},{0, -1} };
  
  void dfs(int x, int y, int[][] picture) {
    int nx, ny;
    for (int d = 0; d < 4; d++) {
      nx = x + dir[d][0];
      ny = y + dir[d][1];
      if(nx >= 0 && ny >= 0 && nx < M && ny < N && !visited[nx][ny] && picture[nx][ny] == picture[x][y]) {
        visited[nx][ny] = true;
        cnt++;
        dfs(nx, ny, picture);
      }
    }
  }
}