단지번호 붙이기

제출코드(정답)

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

public class Main {
    static int[][] map;
    static boolean[][] visited;
    static int N = 0;
    static int totalCount;
    static int attributeCount;
    static List<Integer> attributeCountContainer;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        visited = new boolean[N][N];

        for (int i = 0; i < N; i++) {
            String line = br.readLine(); // 한 줄을 읽어서
            for (int j = 0; j < N; j++) {
                map[i][j] = line.charAt(j) - '0'; // 각 문자를 숫자로 변환하여 저장
            }
        }

        totalCount = 0; // 총 집합 개수
        attributeCountContainer = new ArrayList<>(); // 요소 개수

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                // 요소가 1이고, 방문하지 않았다면
                if (map[i][j] == 1 && visited[i][j] == false) {
                    // 요소 개수 초기화
                    attributeCount = 0;
                    dfs(i,j);
                    totalCount++;
                    attributeCountContainer.add(attributeCount);
                }
            }
        }

        Collections.sort(attributeCountContainer);

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(totalCount + "\n");

        for (int i : attributeCountContainer) {
            bw.write(i + "\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }

    static void dfs(int startX, int startY) {
        visited[startX][startY] = true; // 현재 위치 방문처리
        attributeCount++;

        // 상하좌우
        int[] X = {0,0,-1,+1};
        int[] Y = {-1,+1,0,0};

        for (int i = 0; i < 4; i++) {
            int x = startX + X[i];
            int y = startY + Y[i];

            // 1. 0보다 작거나 N 이상인 경우 건너뛴다.
            if (x < 0 || x >= N || y < 0 || y >= N) {
                continue;
            }

            // 2. 인접한 위치에 1이 있고, 아직 방문하지 않았다면
            if (map[x][y] == 1 && visited[x][y] == false) {
                dfs(x,y); // 재귀적으로 DFS 수행
            }
        }
    }
}

유기농 배추와 흡사해서 큰 어려움은 없었다.

배운점

1. attributeCount는 하나의 요소를 탐색을 완료하면 1이 올라가야 한다.

• dfs()를 실행하면 attributeCount를 1 더해준다.
  만약 요소가 1개인 경우 그 다음 반복이 없더라도 attributeCount는 1이 된다.
• attributeCount = 0;을 main에 있는 dfs() 실행 이전에 작성하여서 dfs() 실행마다 초기화 시켜주었다.

2. 010101 과 같은 String을 숫자로 파싱하기:

for (int j = 0; j < N; j++) {
    map[i][j] = line.charAt(j) - '0'; // 각 문자를 숫자로 변환하여 저장
}

문자로 표현된 숫자에서 문자 '0'을 빼면, 실제 숫자 값이 된다.
이는 ASCII 코드 값의 차이를 이용한 것이다.
예를 들어, 문자 '1'에서 '0'을 빼면, 49 - 48 = 1이 되어 문자 '1'이 실제 숫자 1로 변환된다.

for (int j = 0; j < N; j++) {
    map[i][j] = Character.getNumericValue(line.charAt(j)); // 각 문자를 숫자로 변환하여 저장
}

근데 난 이게 더 편한 것 같다.