백준 2667번 단지번호붙이기

문제 링크

https://www.acmicpc.net/problem/2667

문제 분류

• 그래프 탐색
• bfs

문제 풀이

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Pair {
    int x;
    int y;
    Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class Baekjoon2667 {
    private static final int[] dx = {0, 0, 1, -1}; // 상하좌우 이동을 위한 x축 배열
    private static final int[] dy = {1, -1, 0, 0}; // 상하좌우 이동을 위한 y축 배열

    private static Scanner sc = new Scanner(System.in);

    private static void bfs(int[][] map, int[][] group, int x, int y, int cnt, int sizeOfMap) {
        Queue<Pair> q = new LinkedList<>();
        q.add(new Pair(x, y));
        group[x][y] = cnt;

        while (!q.isEmpty()) {
            Pair p = q.remove();
            x = p.x;
            y = p.y;

            for (int k=0; k<4; k++) { // 위, 아래, 오른쪽, 왼쪽
                int nx = x + dx[k]; // 이동 후 x축 좌표값
                int ny = y + dy[k]; // 이동 후 y축 좌표값
                
                if (isValidLocation(sizeOfMap, nx, ny)) { // 이동 후 좌표값이 지도 안에 위치하는지 확인
                    if (map[nx][ny] == 1 && group[nx][ny] == 0) {
                        q.add(new Pair(nx, ny));
                        group[nx][ny] = cnt;
                    }
                }
            }
        }
    }

    private static boolean isValidLocation(int sizeOfMap, int nx, int ny) {
        return 0 <= nx && nx < sizeOfMap && 0 <= ny && ny < sizeOfMap;
    }

    public static void main(String[] args) {
        // 지도 크기 입력받아서 크기만큼 2차원 배열 초기회
        int sizeOfMap = Integer.parseInt(sc.nextLine()); // 지도 크기 : sizeOfMap * sizeOfMap
        int[][] map = new int[sizeOfMap][sizeOfMap]; // map[i][j] : 1(집이 있는 곳), 0(집이 없는 곳).

        // 집이 있는 곳, 없는 곳에 대한 정보를 입력값을 받는다.
        completedMapWithInput(sizeOfMap, map);

        int cnt = 0; // 몇 단지인지 표시하기 위한 변수
        int[][] group = new int[sizeOfMap][sizeOfMap]; // 지도 내 각 좌표값에 대한 탐색 결과를 저장하기 위한 배열
        for (int i = 0; i < sizeOfMap; i++) {
            for (int j = 0; j < sizeOfMap; j++) {
                if (map[i][j] == 1 && group[i][j] == 0) { // 집이 있는 곳이고, 방문한 적이 없는 경우.
                    bfs(map, group, i, j, ++cnt, sizeOfMap);
                }
            }
        }

        int[] ans = new int[cnt]; // 각 단지내 집의 수를 구하기
        for (int i=0; i<sizeOfMap; i++) {
            for (int j=0; j<sizeOfMap; j++) {
                if (group[i][j] != 0) {
                    ans[group[i][j]-1] += 1;
                }
            }
        }

        Arrays.sort(ans); // 최종 출력을 위해 단지 내 집의 수를 오름차순으로 정렬
        System.out.println(cnt);
        Arrays.stream(ans).forEach(System.out::println);
    }

    private static void completedMapWithInput(int sizeOfMap, int[][] map) {
        for (int i = 0; i < sizeOfMap; i++) {
            String s = sc.nextLine(); // map 한 줄씩 입력받기
            for (int j = 0; j < sizeOfMap; j++) {
                map[i][j] = s.charAt(j) - '0';
            }
        }
        sc.close();
    }
}