[BOJ_2667] 단지번호붙이기(java)

문제

• 정사각형 모양의 지도에서 1은 집이 있는 곳, 0은 집이 없는 곳
• 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력

어려웠던 점

• 문자열 숫자를 숫자로 map에 저장
• 각 단지에 속하는 집의 수 정렬, 출력

1. 문자열 숫자로 변환하기

• str.charAt(j) - '0';
  문자열 숫자로 변환

2. 각 단지에 속하는 집의 수 정렬, 출력

1) 집의 수를 저장할 ArrayList 선언
2) bfs 탐색에서 새로운 집을 발견할 때마다 수 증가시키고 return
3) 각 단지를 발견할 때마다 해당 단지의 집 수를 리스트에 추가
4) 모든 단지 탐색한 후 리스트를 정렬하고 각 단지의 집 수를 순서대로 출력

Collections.sort(houseCount);
for(int houses : houseCount){
	System.out.println(houses);
}

전체코드

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

public class BOJ_2667 {

    static int[] dx = {-1, 1, 0, 0}; // 상 하 좌 우
    static int[] dy = {0, 0, -1, 1};

    static int N; // N : 지도의 크기
    static int[][] map;
    static int[][] visited;
    static String str;
    static int count;
    static ArrayList<Integer> houseCount = new ArrayList<>();


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        visited = new int[N][N];

        for(int i = 0; i < N; i++){
            str = br.readLine();
            for(int j = 0; j < N; j++){
                map[i][j] = str.charAt(j) - '0';
            }
        }

        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                if(map[i][j] == 1 && visited[i][j] == 0){
                    count++;
                    int houses = bfs(i,j);
                    houseCount.add(houses);
                }
            }
        }
        System.out.println(count);

        Collections.sort(houseCount);
        for(int houses : houseCount){
            System.out.println(houses);
        }
    }

    public static int bfs(int x, int y) {
        int houseCount = 0;
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[] {x,y});
        visited[x][y] = 1;

        while(!queue.isEmpty()){
            int[] current = queue.poll();
            int cx = current[0];
            int cy = current[1];
            houseCount++;

            for(int i = 0; i < 4; i++){
                int nx = cx + dx[i];
                int ny = cy + dy[i];
                if(nx < 0 || ny < 0 || nx >= N || ny >= N){
                    continue;
                }
                if(visited[nx][ny] == 1 || map[nx][ny] == 0){
                    continue;
                }
                queue.offer(new int[] {nx, ny});
                visited[nx][ny] = 1;
            }
        }
        return houseCount;
    }
}

느낀점

• BFS 구현 감이 살아있음을 느꼈다 !!
• 총 단지수, 각 단지내 집의 수와 같이 부가적으로 처리해주는 작업이 부족하다고 느껴졌다 ...