[백준(JAVA)] 2667번: 단지번호붙이기

문제

✔ 난이도 - Silver 1

설명

(0,0) ~ (N,N) 확인하면서 1인 좌표에서 시작.
오른쪽 -> 아래 -> 왼쪽 -> 위 순서대로 탐색
탐색한 부분이 1이면 그 위치로 가서 또 다시 탐색. 이 떄 탐색했다는 의미로 숫자를 0으로 변경해줌.
만약 탐색해도 1이 없으면 백트래킹 됨

풀이

public class Main {

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

        int N = Integer.parseInt(br.readLine());
        int[][] graph = new int[N][N];

        String str;
        for (int i = 0; i < N; i++){
            str = br.readLine();
            char[] arr = str.toCharArray();
            for (int j = 0; j < N; j++){
                graph[i][j] = arr[j] - '0';
            }
        }
        // 숫자 넣기 완료

        int[] rotateRow = {0, 1, 0, -1};
        int[] rotateCol = {1, 0, -1, 0};

        int count = 0;
        ArrayList<Integer> house = new ArrayList<>();
        for (int i = 0; i < N; i++){
            for (int j = 0; j < N; j++){
                if (graph[i][j] == 0) continue;
                count++;
                int h = 1;

                h = bt(graph, rotateRow, rotateCol, i, j, N);
                house.add(h);
            }
        }

        sb.append(count).append("\n");

        house.sort((a,b) -> a.compareTo(b));
        for (int i = 0; i < house.size(); i++){
            sb.append(house.get(i)).append("\n");
        }

        System.out.println(sb);
    }

    private static int bt(int[][] graph, int[] rotateRow, int[] rotateCol, int row, int col, int N) {
        if (row < 0 || col < 0 || row >= N || col >= N || graph[row][col] == 0) return 0;
        graph[row][col] = 0;
        int count = 1;

        for (int k = 0; k < 4; k++){
            count += bt(graph, rotateRow, rotateCol, row + rotateRow[k], col + rotateCol[k], N);
        }

        return count;
    }
}

단지 내 집 수를 구하기 위해 처음에는 h를 인자로 넘기면서 계산했는데, 재귀 함수 구조상 h를 인자로 계속 들고 다니면 값이 꼬일 수 있다. (실제로 이것 때문에 계속 틀림)

• 문제점: h += bt(...)를 할 때, 안쪽에서 h를 또 더하고 밖에서도 더하면 숫자가 기하급수적으로 커질 위험이 있음
• 해결: h 인자를 아예 없애고, 현재 칸(1) + 주변에서 찾은 칸들을 리턴하게 만드는 것이 가장 깔끔

private static int bt(int[][] graph, int h, int[] rotateRow, int[] rotateCol, int row, int col, int N) {
    ...

    graph[row][col] = 0; // 방문 처리 (중복 방지)
    int count = 1; // 현재 칸 1개

    for (int k = 0; k < 4; k++) {
        // 주변에서 찾은 집의 개수를 계속 더해줌
        count += bt(graph, h, rotateRow, rotateCol, row + rotateRow[k], col + rotateCol[k], N);
    }

    return count;
}

⏰ 시간복잡도

$O(N^2)$ (정확히는 정렬 포함 시 $O(N^2 \log N)$)

코드의 흐름을 보면 중첩 for문 안에 재귀(DFS)가 있어서 $N \times N \times N$처럼 느껴질 수 있으나 핵심은 graph[row][col] = 0; 이 한 줄에 있음

• 중첩 for문: 모든 칸($N^2$개)을 한 번씩 훑는다
• 재귀(bt) 함수: 1인 칸을 만나면 호출됨
• 하지만 호출되자마자 해당 칸을 0으로 바꿔버림 (방문 처리)
• 이후 중첩 for문이 다음 칸으로 이동했을 때, 이미 방문한 칸은 if (graph[i][j] == 0) continue;에 걸려 무시된다.
• 결과적으로 모든 칸은 전체 프로그램 통틀어 딱 한 번씩만 방문된다.

따라서 전체 탐색 시간 복잡도는 $O(N^2)$

정렬 복잡도까지 고려한다면 단지의 개수를 $K$라고 할 때, 마지막에 house.sort()를 수행

• 최악의 경우 단지의 개수는 $N^2$에 비례할 수 있음 (예: 체크판 모양)
• 정렬 알고리즘의 시간 복잡도는 $O(K \log K)$
• 따라서 전체 시간 복잡도는 $O(N^2 \log N^2)$, 즉 $O(N^2 \log N)$

작업	시간 복잡도	이유
지도 읽기	$O(N^2)$	이중 for문
단지 탐색(DFS)	$O(N^2)$	모든 칸을 딱 한 번씩만 방문
단지 정렬	$O(N^2 \log N)$	단지 리스트 정렬 (최악의 경우)
전체 복잡도	$O(N^2 \log N)$	$N=25$일 때 약 625회 연산 (매우 빠름)

💡 TIL

StringTokenizer의 delim은 빈문자열""을 인식하지 못함

StringTokenizer는 인자로 넘겨준 구분자(Delimiter)를 기준으로 문자열을 자르는 도구
그러나 ""(빈 문자열)을 구분자로 넣으면, StringTokenizer는 자를 기준이 없다고 판단해서 전체를 하나의 덩어리로 가져온다.

• String.split("") 사용
  문자열의 split 메서드에 빈 문자열을 넣으면 한 글자씩 잘라서 배열로 만들어줌

String line = br.readLine(); // "0110100"
String[] arr = line.split(""); // ["0", "1", "1", "0", "1", "0", "0"]

// 숫자로 쓰고 싶다면?
int firstNum = Integer.parseInt(arr[0]);

• 🌟 charAt(i) - '0' 사용
  문자(char)에서 '0'을 빼면 실제 정수(int) 값이 된다.

String line = br.readLine();
for (int i = 0; i < line.length(); i++) {
    int num = line.charAt(i) - '0'; // '0'은 48, '1'은 49이므로 빼면 0, 1이 됨
    graph[row][i] = num;
}

• toCharArray() 사용

char[] charArr = br.readLine().toCharArray(); // ['0', '1', '1', ...]

// 접근할 때
if (charArr[0] - '0' == 1) { ... }

|| OR 연산자 왼쪽부터 검사

자바(를 포함한 대부분의 언어)는 || (OR) 연산을 할 때 왼쪽부터 오른쪽으로 검사한다.

private static int bt(int[][] graph, int h, int[] rotateRow, int[] rotateCol, int row, int col, int N) {
    // ❌ 여기서 에러 발생! row나 col이 -1이나 N일 때 graph[row][col]을 먼저 확인하려고 함
    if (graph[row][col] == 0 || row < 0 || col < 0 || row >= N || col >= N) return 0;

만약 row가 -1인 상태로 들어오면, 컴퓨터는 row < 0인지를 보기 전에 graph[-1][col]이 0인지를 먼저 확인하려다가 -1번 인덱스가 없음을 보고 에러를 던지게 됨.
범위를 먼저 체크하고, 그 다음에 값을 확인하자!!!