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

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

1. 문제 분석

문제 개요:
N x N 크기의 지도에서 1은 집이 있는 곳, 0은 집이 없는 곳을 나타냅니다. 1들이 상하좌우로 연결된 집합을 단지라 부르며, 이 단지들의 수와 각 단지에 속하는 집의 수를 구하는 문제입니다.

입력 형식:

1. 첫 줄에 지도의 크기 N이 주어집니다.
2. 다음 N줄에는 N개의 0 또는 1로 이루어진 지도가 주어집니다.

출력 형식:

• 첫째 줄에 단지의 수를 출력합니다.
• 둘째 줄부터 각 단지에 속하는 집의 수를 오름차순으로 출력합니다.

2. 알고리즘 종류

이 문제는 "그래프 탐색(DFS 또는 BFS)" 문제입니다. 각 지점을 방문하면서 1로 연결된 모든 지점을 탐색하고, 방문한 지점들을 하나의 단지로 묶어 단지의 크기를 계산합니다.

3. 주요 부분 및 코드 작성 방법

1. DFS 탐색을 위한 방향 배열 설정:

• 상, 하, 좌, 우로 이동하기 위한 방향 배열 dx와 dy를 설정합니다.

2. 방문 배열과 지도 초기화:

• visited 배열을 통해 이미 방문한 지점을 추적합니다.
• map 배열에 지도의 상태를 저장합니다.

3. DFS 구현:

• 현재 지점에서 시작해 상하좌우로 이동하며 연결된 모든 1들을 탐색합니다.
• 새로운 단지를 발견할 때마다 단지에 속한 집의 수를 계산해 answer 리스트에 추가합니다.

4. 결과 출력:

• 단지의 수와 각 단지에 속하는 집의 수를 오름차순으로 출력합니다.

4. 코드 설명

DFS 함수 (dfs()):

public static void dfs(int x, int y) {
    visited[x][y] = true; // 현재 위치 방문 처리
    for(int k = 0; k < 4; k++) { // 4방향으로 탐색
        int nx = x + dx[k]; // 새로운 x 좌표
        int ny = y + dy[k]; // 새로운 y 좌표
        // 범위를 벗어나거나 이미 방문했으면 건너뜀
        if(nx < 0 || ny < 0 || nx >= N || ny >= N || visited[nx][ny]) continue;
        if(map[nx][ny] == 1) { // 연결된 집이 있으면
            cnt++; // 집의 수 증가
            visited[nx][ny] = true; // 새로운 위치 방문 처리
            dfs(nx, ny); // 재귀적으로 탐색
        }
    }
}

• 현재 위치 x, y에서 시작해 상하좌우 방향으로 이동하며 연결된 1들을 재귀적으로 방문합니다.
• 방문한 지점은 visited 배열에 기록하고, 단지에 속한 집의 수를 cnt 변수로 누적합니다.

메인 함수 (main()):

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    List<Integer> answer = new ArrayList<>(); // 단지 별 집의 수를 저장할 리스트
    N = Integer.parseInt(br.readLine()); // 지도의 크기 N 입력
    map = new int[N][N]; // 지도 배열 초기화
    visited = new boolean[N][N]; // 방문 체크 배열 초기화

    // 지도 정보 입력 받기
    for(int i = 0; i < N; i++) 
        map[i] = Stream.of(br.readLine().split("")).mapToInt(Integer::parseInt).toArray();

    // 지도의 모든 위치 탐색
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            cnt = 1; // 단지 내 집의 수 초기화
            if(map[i][j] == 1 && !visited[i][j]) { // 아직 방문하지 않은 집 발견 시
                dfs(i, j); // DFS 실행
                answer.add(cnt); // 단지 내 집의 수 저장
            }
        }
    }

    Collections.sort(answer); // 단지 내 집의 수를 오름차순 정렬
    System.out.println(answer.size()); // 단지 수 출력
    for(int n : answer) System.out.println(n); // 각 단지의 집 수 출력
}

• 입력을 받아 지도를 초기화하고, 각 지점을 탐색하여 새로운 단지를 찾을 때마다 DFS를 수행합니다.
• answer 리스트에 각 단지의 집의 수를 추가한 후, 정렬하여 출력합니다.

5. 전체 코드

package BOJ.BOJ2667_240824;

import java.io.*;
import java.util.*;
import java.util.stream.Stream;

public class Main {
    static int N, cnt; // 지도 크기와 단지 내 집의 수
    static int[][] map; // 지도 배열
    static boolean[][] visited; // 방문 체크 배열
    // 상하좌우 탐색을 위한 방향 벡터
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {-1, 1, 0, 0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        List<Integer> answer = new ArrayList<>(); // 단지별 집의 수를 저장할 리스트
        N = Integer.parseInt(br.readLine()); // 지도의 크기 입력
        map = new int[N][N]; // 지도 배열 초기화
        visited = new boolean[N][N]; // 방문 체크 배열 초기화

        // 지도 정보 입력 받기
        for(int i = 0; i < N; i++) 
            map[i] = Stream.of(br.readLine().split("")).mapToInt(Integer::parseInt).toArray();

        // 지도의 모든 위치 탐색
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                cnt = 1; // 단지 내 집의 수 초기화
                if(map[i][j] == 1 && !visited[i][j]) { // 방문하지 않은 집이 있으면
                    dfs(i, j); // DFS 실행
                    answer.add(cnt); // 단지 내 집의 수 저장
                }
            }
        }

        Collections.sort(answer); // 단지 내 집의 수를 오름차순 정렬
        System.out.println(answer.size()); // 단지 수 출력
        for(int n : answer) System.out.println(n); // 각 단지의 집 수 출력
    }

    // DFS 탐색 함수
    public static void dfs(int x, int y) {
        visited[x][y] = true; // 현재 위치 방문 처리
        for(int k = 0; k < 4; k++) { // 4방향으로 탐색
            int nx = x + dx[k]; // 새로운 x 좌표
            int ny = y + dy[k]; // 새로운 y 좌표
            // 범위를 벗어나거나 이미 방문했으면 건너뜀
            if(nx < 0 || ny < 0 || nx >= N || ny >= N || visited[nx][ny]) continue;
            if(map[nx][ny] == 1) { // 연결된 집이 있으면
                cnt++; // 집의 수 증가
                visited[nx][ny] = true; // 새로운 위치 방문 처리
                dfs(nx, ny); // 재귀적으로 탐색
            }
        }
    }
}