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

2667번: 단지번호붙이기

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

 

# DFS 코드

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

public class Main {
	// 지도 정보 및 방문 여부 체크
	static int[][] danji;            // 지도 배열 (1: 집, 0: 빈 공간)
	static boolean[][] visited;      // 해당 좌표를 방문했는지 여부

	// 방향벡터: 상하좌우
	static int[] dx = {0, 0, -1, 1}; // 행 이동 (위, 아래)
	static int[] dy = {-1, 1, 0, 0}; // 열 이동 (좌, 우)

	static List<Integer> result;     // 단지별 집의 수 저장 리스트
	static int cnt, N;               // cnt: 단지에 포함된 집 수, N: 지도 크기

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  // 입력
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); // 출력
		
		result = new LinkedList<>(); 
		N = Integer.parseInt(br.readLine());  // 지도의 크기 입력
		danji = new int[N][N];                // 지도 배열 생성
		visited = new boolean[N][N];          // 방문 배열 생성
		cnt = 1;                              // DFS 시작점 포함하므로 1로 초기화
		
		// 지도 정보 입력 받기
		for (int i = 0; i < N; i++) {
			String str = br.readLine();       // 한 줄 입력
			for (int j = 0; j < N; j++) {
				danji[i][j] = str.charAt(j) - '0'; // 문자 '0' 또는 '1'을 숫자로 변환
			}
		}
		
		// 지도 전체를 탐색
		for (int x = 0; x < N; x++) {
			for (int y = 0; y < N; y++) {
				// 집이 있고 아직 방문하지 않았다면 -> 새로운 단지 발견
				if (danji[x][y] == 1 && !visited[x][y]) {
					dfs(x, y);         // DFS 탐색 시작
					result.add(cnt);   // 단지 내 집 수 리스트에 추가
					cnt = 1;           // 다음 단지를 위해 cnt 초기화
				}
			}
		}
		
		Collections.sort(result); // 오름차순 정렬
		
		bw.write(result.size() + "\n"); // 단지 수 출력
		for (int r : result) {
			bw.write(r + "\n"); // 각 단지의 집 수 출력
		}
		bw.flush();
		bw.close();
	}

	// DFS 함수
	public static void dfs(int x, int y) {
		visited[x][y] = true; // 현재 좌표 방문 처리

		// 상하좌우 탐색
		for (int i = 0; i < 4; i++) {
			int nx = dx[i] + x; // 다음 x좌표
			int ny = dy[i] + y; // 다음 y좌표

			// 배열 범위 체크 + 아직 방문 안 했고 + 집(1)이 있을 때만 이동
			if (nx >= 0 && ny >= 0 && nx < N && ny < N 
			    && !visited[nx][ny] && danji[nx][ny] == 1) {
				cnt++;            // 단지 내 집 개수 증가
				dfs(nx, ny);      // 다음 집으로 DFS
			}
		}
	}
}

 

 

# BFS 코드

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

public class Main {
    static int[][] map; // 지도 배열 (0: 집 없음, 1: 집 있음)
    static boolean[][] visited; // 방문 여부 체크 배열
    static int n; // 지도의 크기 (n x n)
    static int[] dx = { -1, 1, 0, 0 }; // 행 변화 (상, 하)
    static int[] dy = { 0, 0, -1, 1 }; // 열 변화 (좌, 우)
    static List<Integer> result = new ArrayList<>(); // 결과를 저장할 리스트 (각 단지에 속한 집의 수)

    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'; // 문자 '1' → 숫자 1
            }
        }

        // 전체 탐색 시작
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
            	// 집이 있고, 아직 방문하지 않았다면 → 새로운 단지 발견!
                if (map[i][j] == 1 && !visited[i][j]) {
                    int count = bfs(i, j); // 단지 하나에 대해 BFS로 연결된 집 수 세기
                    result.add(count);     // 단지리스트에 집 수 저장
                }
            }
        }

        // 단지별 집의 수를 오름차순으로 정렬
        Collections.sort(result);

        // 출력
        System.out.println(result.size()); // 단지 수
        for (int r : result) {
            System.out.println(r); // 각 단지의 집 수
        }
    }

    // BFS 함수: 시작 좌표 (x, y)부터 연결된 집들 탐색
    static int bfs(int x, int y) {
        Queue<int[]> queue = new LinkedList<>(); // 탐색을 위한 큐 생성
        queue.offer(new int[]{x, y}); // 시작점 큐에 넣기
        visited[x][y] = true; // 시작점 방문 처리

        int count = 1; // 이 단지에 속한 집의 수 (시작점 포함해서 1)

	// 큐가 빌 때까지 반복
        while (!queue.isEmpty()) {
        // 현재 위치 꺼내기
            int[] curr = queue.poll();
            int currX = curr[0];
            int currY = curr[1];

            // 상하좌우 방향 탐색
            for (int i = 0; i < 4; i++) {
                int nextX = currX + dx[i];
                int nextY = currY + dy[i];

                // 1. 범위 벗어나면 건너뜀
                if (nextX < 0 || nextY < 0 || nextX >= n || nextY >= n) {
                    continue;
                }

                // 2. 이미 방문했거나, 집이 없는 경우 건너뜀
                if (visited[nextX][nextY] || map[nextX][nextY] == 0) {
                    continue;
                }

                // 3. 연결된 집이라면
                visited[nextX][nextY] = true;        // 방문 처리
                queue.offer(new int[]{nextX, nextY}); // 큐에 추가
                count++;                             // 집 수 증가
            }
        }

        return count; // 이 단지에 속한 집의 총 개수 반환
    }
}