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

문제

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

---

코드

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

public class Main {
    private static int[][] map;
    private static boolean[][] visited;
    private static int N;
    private static int[] dx = {-1, 1, 0, 0};
    private static int[] dy = {0, 0, 1, -1};


    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 < line.length(); j++) {
                map[i][j] = Integer.parseInt(String.valueOf(line.charAt(j)));
            }
        }

        List<Integer> result = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                int num = dfs(i, j);
                if (num != 0) result.add(num);
            }
        }

        Collections.sort(result);

        StringBuilder sb = new StringBuilder();
        sb.append(result.size()).append("\n");
        for (Integer ans : result) {
            sb.append(ans).append("\n");
        }

        System.out.println(sb);
    }


    private static int dfs(int x, int y) {
        if (!isValid(x, y)) return 0;
        if (map[x][y] == 0) return 0;

        visited[x][y] = true;
        int count = 1;

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            count += dfs(nx, ny);
        }
        return count;
    }

    private static boolean isValid(int x, int y) {
        return x >= 0 && x < N && y >= 0 && y < N && !visited[x][y];
    }
}

---

풀이

`dfs` 함수

private static int dfs(int x, int y) {
    if (!isValid(x, y) || map[x][y] == 0) return 0;
    visited[x][y] = true;
    int count = 1;
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        count += dfs(nx, ny);
    }
    return count;
}

• `isValid(x, y)` → 범위를 벗어나거나 이미 방문된 값은 탐색 제외
• `map[x][y] == 0`인 칸 → 집이 없는 칸 탐색 제외
• 위 조건을 모두 통과하면 방문 처리(`visited[x][y] = true`) 후 `count = 1`로 시작(개수 카운트)
• 상하좌우 네 방향으로 재귀 호출하여 주변에 연결된 집의 개수를 누적(`count += dfs(nx, ny)`)

 

`dfs` 함수가 반환하는 값이 0이 아닌 경우에만, `result` 리스트에 추가한다. 그리고 마지막에 `result`를 오름차순 정렬한 뒤, 각 단지의 크기를 한 줄 씩 출력하면 된다.