[백준] 2667 단지번호붙이기

문제보기

import java.util.*;

// 좌표를 나타낼 클래스
class Pair{
  int x;
  int y;
  Pair(int x, int y){
    this.x = x;
    this.y = y;
  }
}

public class Main
{
  //combinations of dx & dy make 4 directions. 
  public static int[] dx = {0, 0, 1, -1};
  public static int[] dy = {1, -1, 0, 0};

  public static void bfs(int[][] a, int[][] group,
                         int x, int y, int cnt, int n){
    Queue<Pair> q = new LinkedList<Pair>();
    q.add(new Pair(x, y));
    group[x][y] = cnt;

    while(!q.isEmpty()){
      Pair p = q.remove(); //current spot
      x = p.x; //insert into x, y to make next spot
      y = p.y;

      for(int k = 0 ; k < 4 ; k++ ){ //check only 4 cases
        int nx = x + dx[k];
        int ny = y + dy[k];

        //if next spot is on the map
        if( 0 <= nx && nx < n && 
           0 <= ny && ny < n ){

          //if there is a house & not belongs to otehr groups
          if(a[nx][ny] == 1 && group[nx][ny] == 0){
            q.add(new Pair(nx, ny)); 
            group[nx][ny] = cnt; //grouping
          }
        }
      }
    }
  }


  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    sc.nextLine(); //enter 

    // get a map from text
    int[][] a = new int[n][n];

    for(int i = 0; i < n ; i++){
      //get line by line
      String s = sc.nextLine();
      for(int j = 0 ; j < n ; j++ ){
        a[i][j] = s.charAt(j) - '0'; //ascii 
      }
    }

    int cnt = 0;
    int[][] group = new int[n][n]; //group saves result map
    
    for(int i = 0 ; i < n ; i++){
      for(int j = 0 ; j < n ; j++ ){
        if(a[i][j] == 1 && group[i][j] == 0){
          //if there is a house and not belongs to any other group
          bfs(a,group, i, j , ++cnt, n);
        }
      }
    }

    int[] ans = new int[cnt]; 
    //ans saves result text (number of houses by groups)
    for(int i = 0 ; i < n ; i++ ){
      for(int  j = 0 ; j < n ; j++ ){
        if(group[i][j] != 0){
          ans[group[i][j]-1]++;
        }
      }
    }

    Arrays.sort(ans);
    System.out.println(cnt); //total number of groups
    for(int i = 0 ; i < cnt ; i++ ){
      System.out.println(ans[i]);
    }
  }
}

가끔 한영전환 귀찮으면 콩글리시로 주석답니다..