59 삐약 : 백준 2667| 단지번호붙이기 [바킹독 문제 풀이|BFS|JAVA]

 

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

 

package BKD_0x9_BFS;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BOJ_2667 {
    static int N;
    static char[][] apts;

    static int[] dx ={0,1,0,-1};
    static int[] dy ={1,0,-1,0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        apts = new char[N][N];
        ArrayList<Integer> NOH = new ArrayList<>(); // num of house

        for(int i=0;i<N;i++){
            String input = br.readLine();
            for(int j=0;j<N;j++){
                apts[i][j] = input.charAt(j);
            }
        }

        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(apts[i][j]=='1'){
                    int num = bfs(i,j);
                    NOH.add(num);
                }
            }
        }

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



    }

    public static int bfs(int x, int y){
        Queue<Pair> q = new LinkedList<>();
        q.offer(new Pair(x,y));
        apts[x][y]='0';
        int count=1;

        while (!q.isEmpty()){
            Pair p = q.poll();

            for(int i=0;i<4;i++){
                int nx = p.x+dx[i];
                int ny = p.y+dy[i];

                if(nx>=0 && ny>=0 && nx<N && ny<N && apts[nx][ny]=='1'){
                    apts[nx][ny]='0';
                    q.offer(new Pair(nx,ny));
                    count++;
                }
            }

        }
        return count;

    }

    public static class Pair{
        int x;
        int y;

        public Pair(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
}

 

 

이 직전에 풀은 문제랑 똑띠똑띠싱크로융원헌덜펄센이라서 그냥 EZPZ 레몽스퀘제 하게 슥삭 해결하였따