Baekjoon | Q.2667 - 단지번호붙이기

2667번: 단지번호붙이기

 깊이우선탐색(DFS)를 이용해서 아파트 단지가 몇개인지, 각 단지에는 아파트가 몇개인지 찾는 문제이다. 

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {
  static int N; // 지도의 크기
  static int[][] map; // 지도
  static boolean[][] visit; // 방문 여부 저장
  static int[] dx = {0, 1, 0, -1};  // 한 아파트를 기준으로 시계방향으로 탐색
  static int[] dy = {-1, 0, 1, 0};

  static int home = 0;  // 아파트 갯수를 저장할 변수
  static ArrayList<Integer> answer = new ArrayList<>(); // 단지 별 아파트 갯수를 저장할 리스트
  public static void main(String[] args) {
    // 입력
    Scanner sc = new Scanner(System.in);
    N = sc.nextInt();
    map = new int[N][N];
    visit = new boolean[N][N];

    for (int i = 0; i < N; i++) {
      String row = sc.next();
      for (int j = 0; j < N; j++) {
        int n = Integer.parseInt(row.charAt(j) + "");
        map[i][j] = n;
      }
    }

    sc.close();

    // 탐색
    int group = 0;  // 단지 갯수 추가
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
        if(!visit[i][j] && map[i][j] == 1) {
          visit[i][j] = true;
          group++;  // 단지내에서 아파트 찾기 start
          home++; // 시작점 아파트 추가
          dfs(i, j);  // dfs 한 사이클이 끝나면 단지 하나를 찾은것임.
          answer.add(home);
          home = 0; // 다음 단지 탐색을 위해 아파트 갯수 초기화
        }
      }
    }
    
    Collections.sort(answer); // 오름차순 정렬
    
    // 출력
    System.out.println(group);

    for (int i = 0; i < answer.size(); i++) {
      System.out.println(answer.get(i));
    }

  }

  // DFS 알고리즘
  public static void dfs(int x, int y) {  // x, y는 탐색을 시작할 시작점
    for (int k = 0; k < 4; k++) {
      int next_x = x + dx[k];
      int next_y = y + dy[k];
      if(next_x >= 0 && next_x < N && next_y >= 0 && next_y < N) {  // 인덱스가 범위 내에 있는 경우
        if(!visit[next_x][next_y] && map[next_x][next_y] == 1) {  // 방문한 적 없고 연결된 아파트라면
          visit[next_x][next_y] = true; // 방문해서
          home++; // 아파트 갯수 추가
          dfs(next_x, next_y);  // 다음 깊이로 시작점 이동
        }
      }
    }
  }
}

 지도의 상, 하, 좌, 우에 연결된 아파트가 있으면 home count를 증가시키고 dfs를 재귀호출 해주는 방식으로 풀었다. 더 이상 연결된 아파트가 없으면 재귀 호출은 자동 종료된다.