[JAVA/2667번] 단지번호붙이기*

문제

입력 및 출력

풀이

import java.io.*;
import java.util.*;

class Main {
  public static int N;
  public static int[][] map;
  public static boolean[][] visited;
  public static int count;
  public static int[] dx = {0, 1, 0 ,-1};
  public static int[] dy = {1, 0, -1, 0};
  public static void main(String args[]) throws Exception{ 
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    // 단지의 결과를 담을 ArrayList
    ArrayList<Integer> list = new ArrayList<>();

    // N
    N = Integer.parseInt(br.readLine());

    // visited
    visited = new boolean[N][N];

    // map
    map = new int[N][N];
    for(int i = 0; i < N; i++) {
      String[] temp = br.readLine().split("");
      for(int j = 0; j < temp.length; j++) {
        map[i][j] = Integer.parseInt(temp[j]);
      }
    }
    
    for(int i = 0; i < N; i++) {
      for(int j = 0; j < N; j++) {
        if(!visited[i][j] && map[i][j] == 1) {
          // count값 초기화
          count = 0;
          DFS(i, j);
          list.add(count);
        }
      }
    }

    // 오름차순 정렬
    Collections.sort(list);

    // 결과 값 출력
    System.out.println(list.size());
    for(int i : list) {
      System.out.println(i);
    }
  }

  public static void DFS(int x, int y) {
    // 처음으로 방문하는 곳 방문처리
    visited[x][y] = true;
    count++;

    // 자신을 기준으로 좌,우,상,하 탐색
    for(int i = 0; i < 4; i++) {
      int nx = x + dx[i];
      int ny = y + dy[i];

      // 범위가 초과할 경우 넘어가기
      if(nx < 0 || ny < 0 || nx >= N || ny >= N) {
        continue;
      }

      // 방문하지 않았고, 새로운 위치가 1이면 탐색수행
      if(!visited[nx][ny] && map[nx][ny] == 1) {
        visited[nx][ny] = true;
        DFS(nx, ny);
      }
    }
  }
}

결과 및 해결방법

[결과]