[Java] BOJ 2667 단지번호붙이기

문제 

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

• <그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다.
• 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다.
• 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다.
• <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

  

• 첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.
• 첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

아이디어

• 방문하지 않았고 값이 1인 좌표를 기준으로 BFS를 돌린다.
• BFS를 돌리면서 상하좌우를 탐색하여 연결되어 있는 좌표값이 1인 좌표값을 찾고 카운트를 해준 후, 방문처리를 해준다.
• 그렇게 BFS를 돌리고 Queue가 비면 카운트한 변수를 return 해줘서 ArrayList에 담는다 (한 단지에 있는 사람의 수)
• 그렇게 배열을 처음부터 끝까지 돌리면 단지마다 몇명 있는지 ArrayList에 저장이 되는데, 그 ArrayList를 정렬 후 출력한다.

겪은 시행착오

• X

BFS는 이제 나름 풀만 할지도..? ㅎㅎ

코드

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

public class BOJ2667 {

    static int N;
    static int map[][];
    static boolean visited[][];
    static ArrayList<Integer> result;
    static int dx[] = {-1, 1, 0, 0};
    static int dy[] = {0, 0, -1, 1};

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        // 행, 열
        N = Integer.parseInt(br.readLine());
        // 지도
        map = new int[N][N];
        // 방문 여부
        visited = new boolean[N][N];
        // 결과값을 저장할 ArrayList
        result = new ArrayList<>();

        // 지도 입력
        for(int i = 0; i < N; i++){
            String s = br.readLine();
            for(int j = 0; j < N; j++){
                int n = Integer.parseInt(s.split("")[j]);

                map[i][j] = n;
            }
        }

        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                // 만약 해당 좌표를 방문하지 않았는데
                // 값이 1이라면
                if(!visited[i][j] && (map[i][j] == 1)){
                    int cnt = BFS(i, j);

                    // return한 사람수를 ArrayList에 넣어줌
                    result.add(cnt);
                }
            }
        }

        // 오름차순으로 정렬
        Collections.sort(result);

        sb.append(result.size() + "\n");

        for(int i : result){
            sb.append(i + "\n");
        }

        System.out.println(sb);
    }

    public static int BFS(int x, int y){
        Queue<Point> q = new LinkedList<>();

        // 들어온 좌표값을 Queue에 넣어줌
        q.offer(new Point(x, y));

        // 해당 좌표 방문 처리
        visited[x][y] = true;

        // 사람 수
        int people = 1;

        // Queue가 빌때까지
        while(!q.isEmpty()){
            // Queue에 저장된 좌표값
            int xx = q.peek().x;
            int yy = q.peek().y;

            q.poll();

            // 꺼낸 좌표 기준으로 상하좌우 탐색
            for(int i = 0; i < 4; i++){
                // 상하좌우로 이동한 좌표값
                int nx = xx + dx[i];
                int ny = yy + dy[i];

                // 배열 범위값을 벗어나면 continue
                if(nx >= N || nx < 0 || ny >= N || ny < 0){
                    continue;
                }

                // 만약 이동한 좌표값을 아직 방문하지 않았고
                // 값이 1이라면
                if(!visited[nx][ny] && (map[nx][ny] == 1)){
                    // 방문 처리 후
                    visited[nx][ny] = true;
                    // 사람 수 + 1을 하고
                    people = people + 1;
                    // Queue에 해당 좌표값을 넣어줌
                    q.offer(new Point(nx, ny));
                }
            }
        }

        // 카운트한 사람 수 return
        return people;
    }
}