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

 

2667번: 단지번호붙이기

 

 

이전에 해결한 11724번 문제 '연결 요소의 개수' 문제와 유사하다.

[백준] 11724번 - 연결 요소의 개수

 

 

 

정사각형 모양의 지도의 각 1x1구획에 하나의 집이 있을 수도 있고 없을 수도 있으며, 집이 있다면 1을 입력받고 집이 없다면 0을 입력받는다. 하나의 단지를 이루는 조건은 상하좌우로 인접한 경우만을 의미하며 최종적으로 모든 단지의 수와 각 단지에 속하는 집들의 수를 오름차순 출력하면 된다.

 

연결 요소의 개수 문제와 마찬가지로 모든 집에 대하여

i) 집이 있는 곳 인지 ii) 방문한 적이 없는지

확인 후 위 두 조건을 모두 만족한다면 하나의 단지에 대한 순회를 시작한다. 순회하는 방식은 DFS와 BFS 중 BFS를 사용하였다. 

 

처음 문제를 해결 했을 때에는 입력을 받으면서 만약 집이 없는 0 이라면 방문체크를 하는 boolean[][] 배열에 true 값을 넣어서 그래프 순회 시에 큐에 해당 좌표를 넣지 않도록 하였는데, 가독성이 조금 떨어지는 것 같아서 큐에 넣기 전 분기에서 집이 있는지 없는지 (1 or 0) 확인하는 것으로 수정하였다. 

 

각 단지에 대한 집의 수는 우선순위 큐에 담아서 오름차순으로 출력할 수 있도록 하였다.

 

 

 

 

전체 코드

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

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

    static int N;
    static char[][] map;
    static Queue<int[]> que;
    static boolean[][] visited;
    static PriorityQueue<Integer> print;    
    
    public static void main (String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        print = new PriorityQueue<>();
        
        N = Integer.parseInt(br.readLine());
        
        map = new char[N][N];
        visited = new boolean[N][N];
        
        
        for (int i=0; i<N; i++) {
            
            String input = br.readLine();
            
            for (int j=0; j<N; j++) map[i][j] = input.charAt(j);
        }
        
        
        // 단지의 갯수
        int count = 0;
        
        for (int i=0; i<N; i++) {
            for (int j=0; j<N; j++) {
            
            	// 집이 존재하고, 방문한 적이 없다면 새로운 단지의 시작이다.
                if (map[i][j] == '1' && visited[i][j] == false) {
                    print.offer(bfs(i, j));
                    count++;
                }
            }
        }
        
        
        
        sb.append(count + "\n");
        
        while (!print.isEmpty()) {
            sb.append(print.poll() + "\n");
        }
        
        System.out.println(sb);
        
        br.close();
    }    
    
    
    
    
    static int bfs (int y, int x) {
        
        que = new LinkedList<>();
        
        que.offer(new int[]{y, x});
        visited[y][x] = true;
        
        int count = 1;
        
        while (!que.isEmpty()) {
            
            int[] n = que.poll();
            
            for (int i=0; i<4; i++) {
            	
            	int nextY = n[0] + dy[i];
            	int nextX = n[1] + dx[i];
                
                // 정사각형 지도 범위 안에 존재하며, 집도 존재하고 방문한 적이 없으면 같은 단지 내에 존재하는 집이다.
                if (checkRange(nextY, nextX) && map[nextY][nextX] == '1' && visited[nextY][nextX] == false) {
                    visited[nextY][nextX] = true;
                    que.offer(new int[]{nextY, nextX});
                    count++;
                }
            }
        }
        
        return count;
    }
    
    static boolean checkRange (int y, int x) {
    	
    	if (x >= 0 && x < N && y >= 0 && y < N) return true;
    	return false;
    }
}