[BOJ] 2667번 단지번호붙이기 Java 풀이

https://www.acmicpc.net/problem/2667

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class BJ_2667 {
  static int n;
  static int[][] house;
  static boolean[][] visited;
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    n = Integer.parseInt(br.readLine());
    house = new int[n][n];
    visited = new boolean[n][n];
    List<Integer> ans = new ArrayList<>();
    for (int i = 0; i < n; i++) {
      String s = br.readLine();
      for (int j = 0; j < n; j++) {
        house[i][j] = Integer.parseInt(String.valueOf(s.charAt(j)));
      }
    }

    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        int complex = dfs(i, j);
        if (complex != 0) {
          ans.add(complex);
        }
      }
    }

    Collections.sort(ans);
    System.out.println(ans.size());
    for (int i : ans) {
      System.out.println(i);
    }
  }

  static int dfs(int x, int y) {
    if (x < 0 || y < 0 || x >= n || y >= n) return 0;
    if (visited[x][y] || house[x][y] == 0) return 0;
    else {
      visited[x][y] = true;
      return 1 + dfs(x - 1, y) + dfs(x + 1, y) + dfs(x, y - 1) + dfs(x, y + 1);
    }
  }
}

• 학부에서 recursion을 배울 때 기본적으로 배우는 미로찾기와 연결된 픽셀의 blob 수 세기 문제랑 많이 비슷하다.
• 기본적으로 DFS, BFS 방식 모두 쓸 수 있는 문제이다. 나는 DFS 방식으로 풀었다.
• complex를 아파트 단지 1개의 집단이라고 가정하고 ArrayList에 하나씩 집어넣는 방식으로 접근했다. dfs를 통해서 그 단지의 아파트를 모두 접근하고 나면 2중 for문을 통해서 모든 아파트의 주변을 검사할 때 단지에 속한다고 카운트된 아파트는 모두 visited배열을 통해서 방문한 아파트일 것이므로 dfs가 0을 리턴한다. 나는 0이 아닌 그룹만 arrayList에 푸쉬해서 저장했다.