백준 2667. 단지번호붙이기 :: 돼지개발자

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

"단순 BFS"

BFS를 돌려서 상하좌우로 인접해 있는 집들을 탐색한다. 탐색하는 과정에서 각 단지를 넘버링 할 수 있는 변수를 하나 두고, BFS 탐색이 끝날 때마다 변수를 증가 시켜 넘버링을 이루게 한다. 이와 비슷한 형식으로 매 BFS 탐색마다 단지의 개수를 세는 count 변수를 하나 두어 단지의 개수를 세고, 아래 풀이에서는 이 카운트 값을 Array List에 넣어두고, 나중에 sort 하였다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
 
public class Main {
 
    static int N;
    static int[][] map;
    static boolean[][] visited;
    static Queue<Node> q = new LinkedList<>();
    static ArrayList<Integer> list = new ArrayList<>();
    static int[] dx = {0,0,1,-1};
    static int[] dy = {1,-1,0,0};
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        N = Integer.parseInt(br.readLine());
        
        map = new int[N][N];
        visited = new boolean[N][N];
        
        for (int i = 0; i < N; i++) {
            char[] temp = br.readLine().toCharArray();
            for (int j = 0; j < N; j++) {
                map[i][j] = temp[j] - '0';
            }
        }
        
        int mark = 0;
        
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if(map[i][j] == 0 || visited[i][j])
                    continue;
                int cnt = 0;
                visited[i][j] = true;
                q.add(new Node(i, j));
                
                while(!q.isEmpty()) {
                    
                    Node cur = q.poll();
                    cnt++;
                    
                    for (int k = 0; k < 4; k++) {
                        int nx = cur.x + dx[k];
                        int ny = cur.y + dy[k];
                        
                        if(!isRange(nx, ny) || visited[nx][ny] || map[nx][ny] == 0)
                            continue;
                        
                        visited[nx][ny] = true;
                        q.add(new Node(nx, ny));
                    }
                }
                list.add(cnt);
                mark++;
            }
        }
        
        Collections.sort(list);
        System.out.println(mark);
        for(int cnt : list) {
            System.out.println(cnt);
        }
    }
    
    static boolean isRange(int x, int y) {
        if( x < 0 || x >= N || y < 0 || y >= N) return false;
        return true;
    }
}
 
class Node {
    int x;
    int y;
    
    Node(int x, int y) {
        this.x = x;
        this.y = y;
    }
}