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

문제 링크 : https://www.acmicpc.net/problem/2667

이 문제는 처음에는 접근법이 감이 안올 수 있다. 

입력받은 이차원 배열을 하나씩 접근해 나가면서 0 이면 무시하고 1이고 BFS로 접근 이력이 없으면 그 좌표를 기준으로 BFS를 돌리면 된다. 

예제를 기준으로 그림으로 보면 이해가 빨리 된다.

7
0110100
0110101
1110101
0000111
0100000
0111110
0111000

위의 예제 입력으로 표를 만들면 아래 처럼 나온다.

0	1	1	0	1	0	0
0	1	1	0	1	0	1
1	1	1	0	1	0	1
0	0	0	0	1	1	1
0	1	0	0	0	0	0
0	1	1	1	1	1	0
0	1	1	1	0	0	0

좌표 (0, 0) 부터 조회를 한다. 

(0,0) 은 0 이므로 무시하고 다음 좌표 (0, 1) 을 확인한다.

좌표의 값은 1이고 아직 BFS를 돌리지 않았기때문에 이 좌표의 visited[0][1] 은 false 이다.

그럼 이 좌표를 기준으로 BFS를 돌린다.

0	1	1	0	1	0	0
0	1	1	0	1	0	1
1	1	1	0	1	0	1
0	0	0	0	1	1	1
0	1	0	0	0	0	0
0	1	1	1	1	1	0
0	1	1	1	0	0	0

그럼 연두색으로 칠한 부분이 BFS로 조회가 된다. 

조회된 주택은 7개이다. 

조회된 주택의 수는 우선순위 큐에 삽입한다.

우선순위 큐는 저장된 데이터중 우선 순위가 높은 데이터부터 추출해준다. 

따로 정렬을 할 필요가 없으니 편하다고 본다. 

이제 1차 BFS를 조회했고 다시 반복문을 돌면서 다음 좌표를 확인한다.

(0,2) 좌표는 BFS에 접근했던 좌표기 때문에 넘어간다. 

(0,3) 좌표는 0이기에 넘어간다.

(0,4) 좌표는 1이면서 아직 방문안한 좌표다.

(0,4) 좌표를 BFS로 조회하면 아래 빨간색으로 색칠한 부분이 조회되고 조회된 주택수는 8 이다.

조회된 주택수 8은 우선순위큐에 삽입시켜준다. 

0	1	1	0	1	0	0
0	1	1	0	1	0	1
1	1	1	0	1	0	1
0	0	0	0	1	1	1
0	1	0	0	0	0	0
0	1	1	1	1	1	0
0	1	1	1	0	0	0

같은 방법으로 모든 좌표를 확인하다보면 (4, 1)에서 새롭게 1이고 아직 방문하지 않은 좌표가 나온다.

이부분을 BFS로 조회하면 파란색으로 색칠한 부분이 조회되고 조회된 조택수는 9가 나온다.

조회된 주택수 9는 우선순위 큐에 삽입 시켜준다.

0	1	1	0	1	0	0
0	1	1	0	1	0	1
1	1	1	0	1	0	1
0	0	0	0	1	1	1
0	1	0	0	0	0	0
0	1	1	1	1	1	0
0	1	1	1	0	0	0

이제 모든 부분이 조회가 다 됐고 결과를 출력 해주면 끝이 난다.

우선순위 큐의 사이즈가 조회된 단지의 수이고

큐의 값을 하나씩 추출하면 오름차순으로 값이 출력 된다.

소스

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
 
public class Main {
    public static int SIZE;
    public static int[][] danji;
    public static boolean[][] visited;
    
    public static PriorityQueue<Integer> pq;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        SIZE = Integer.parseInt(br.readLine());
        
        danji = new int[SIZE][SIZE];
        visited = new boolean[SIZE][SIZE];
        
        pq = new PriorityQueue<Integer>();
        
        for(int i=0; i < SIZE; i++) {
            String str = br.readLine();
            for(int j=0; j < SIZE; j++) {
                danji[i][j] = Integer.parseInt(str.substring(j, j+1));
            }
        }
        
        // danji를 조회하면서 1이고 방문 기록이 없는 좌표는 새로운 단지의 시작 점
        for(int i=0; i < SIZE; i++) {
            for(int j=0; j < SIZE; j++) {
                if(danji[i][j] == 1 && !visited[i][j]) BFS(i, j);
            }
        }
        // 큐의 사이즈가 단지의 수이다.
        System.out.println(pq.size());
        
        // 우선순위 큐는 작은 수부터 우선적으로 나오기 때문에 큐가 빌때까지 값을 출력하면 된다.
        while(!pq.isEmpty()) {
            System.out.println(pq.poll());
        }
    }
    
    public static void BFS(int y, int x) {
        Queue<int[]> queue = new LinkedList<int[]>();
        queue.offer(new int[] {y, x});
        
        int count = 0;
        while(!queue.isEmpty()) {
            int currY = queue.peek()[0];
            int currX = queue.peek()[1];
            queue.poll();
            
            // 좌표 범위를 초과했는지 확인한다.
            if(currY < 0 || currX < 0 || currY >= SIZE || currX >= SIZE) continue;
            // 해당 좌표가 0 이면 접근하면 안된다.
            if(danji[currY][currX] == 0) continue;
 
            // 방문 이력이 있는지 확인한다.
            if(visited[currY][currX]) continue;
            // 방문 이력을 남기고 카운트를 1 증가 시킨다.
            count += 1;
            visited[currY][currX] = true;
            
            // 근처 상하 좌우 좌표를 큐에 입력한다. 
            queue.offer(new int[] {currY+1, currX});
            queue.offer(new int[] {currY-1, currX});
            queue.offer(new int[] {currY, currX+1});
            queue.offer(new int[] {currY, currX-1});
        }
        // 현재 단지의 수를 우선순위 큐에 삽입한다.
        pq.offer(count);
    }
 
}