[백준] 2667_단지번호 붙이기 java 쉬운 풀이!

1. 문제 설명

문제 설명

2. 접근 방식

KEY WORD: BFS

2차원 배열에 값을 담는다.
번호 별로 의미가 있다. (0 = 벽, 1 = 미방문한 아파트 단지, 2 = 방문한 단지)

(1) 2차원 배열을 순회하다가 값 == 1인 것을 만나면, 해당 값을 시작으로 BFS를 돌린다.

• 현재 값의 사방을 탐색한다.
• 사방의 값 중 1인 값이 있으면 큐에 넣고, 해당 위치의 값을 2로 바꾼다.
• 큐가 빌 때 까지 (더 이상 사방 탐색을 해도 값 = 1이 안 나올 때 까지) 반복한다.

(2) 1번은 첫 조회에서 만난 아파트의 아파트 단지 전체를 한번에 보는 것이다. 따라서 1번의 반복 횟수가 곧 아파트의 개수이다.

(3) 아파트 단지를 단지내 아파트의 개수에 따라 오름차순으로 정렬한다.

3. 코드 분석

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

public class Main {
    // 값 저장
    static int [][] arr;
    // 사방 탐색용
    static int [] idx = new int[]{-1,0,1,0};
    static int [] idy = new int[]{0,1,0,-1};
    // 아파트 단지 개수용
    static int cnt = 0;

    public static void main(String[] args) throws IOException {
        // 입력 받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        ArrayList<Integer> list = new ArrayList<>();
        int N = Integer.parseInt(br.readLine());
        arr = new int[N][N];

        for(int i = 0; i < N; i++){
            String s = br.readLine();
            for (int j = 0; j < N; j++) {
                arr[i][j] = s.charAt(j) - 48;
            }
        }
        // 배열을 조회 했을 때, 값이 1인 값을 만나면 그 값을 기준으로 BFS 돌리기 
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if(arr[i][j] == 1){
                    cnt++;
                    list.add(bfs(new Coordinate(i,j)));
                }
            }
        }
        // 값들을 아파트 개수를 기준으로 오름차순 정렬
        Collections.sort(list);
        System.out.println(cnt);
        for(int temp: list){
            System.out.println(temp);
        }

    }

    public static int bfs(Coordinate now) {
        // 공터: 0, 미방문 단지: 1, 방문한 단지: 2

        // 현재 탐색 중인 아파트단지의 아파트 갯수 카운트  
        int apart_cnt = 1;
        ArrayDeque<Coordinate> aq1 = new ArrayDeque<>();
        // 첫 조회한 아파트를 집어 넣기
        aq1.add(now);
        // 방문 표시
        arr[now.x][now.y] = 2;

        while(!aq1.isEmpty()) {
            Coordinate cur = aq1.poll();
            // 사방 탐색
            for (int i = 0; i < 4; i++) {
                int nx = cur.x + idx[i];
                int ny = cur.y + idy[i];
                // 배열 범위 안이고, 미방문한 아파트라면,
                if(nx>=0 && ny>= 0 && nx< arr.length && ny < arr.length){
                    if(arr[nx][ny] == 1) {
                        // 방문처리 후에 해당 아파트를 기점으로 4방 탐색하기 위해 queue에 넣는다.
                        arr[nx][ny] = 2;
                        aq1.add(new Coordinate(nx,ny));
                        apart_cnt++;
                    }
                }
            }
        }
        return apart_cnt;
    }
}
class Coordinate {
    int x;
    int y;

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