백준 2667번 - 단지번호붙이기 (Java, BFS)

문제 요약

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

• 정사각형 모양의 지도(n × n)가 주어진다.
• 각 칸은 0 또는 1로 표시되어 있으며, 1은 집이 있는 곳 0은 빈 공간이다.
• 상하좌우로 연결된 집들을 하나의 단지로 간주한다.
• 지도에서 총 단지 수를 구하고, 각 단지에 속한 집의 수를 오름차순으로 출력하라.

---

접근 방식

BFS (너비 우선 탐색) 를 이용해 단지를 탐색한다.

• 지도 전체를 순회하면서 방문하지 않은 집(1)이 나타나면 BFS를 시작한다.
• BFS를 통해 상하좌우로 연결된 모든 집을 찾고, 해당 단지의 집 수를 센다.
• 집을 방문할 때마다 0으로 바꿔 재방문을 막는다.
• 각 단지의 집 수를 리스트에 저장하고, 정렬 후 출력한다.

---

전체 코드

import java.util.*;

class Point {
	public int x, y;
	
	Point(int x, int y) {
		this.x = x;
		this.y = y;
	}
}
public class Main {
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = {0, 1, 0, -1};
	static int n;
	
	public void solution(int[][] arr) {
		Queue<Point> q = new LinkedList<>();
		ArrayList<Integer> answer = new ArrayList<>();
		for(int x=0; x<n; x++) {
			for(int y=0; y<n; y++) {
				if(arr[x][y]==1) {
					int count = 1;
					arr[x][y] = 0;
					q.offer(new Point(x, y));
					
					while(!q.isEmpty()) {
						Point tmp = q.poll();
						for(int i=0; i<4; i++) {
							int nx = tmp.x + dx[i];
							int ny = tmp.y + dy[i];
							
							if(nx>=0 && nx<n && ny>=0 && ny<n && arr[nx][ny]==1) {
								arr[nx][ny] = 0;
								count++;
								q.offer(new Point(nx, ny));
							}
						}
					}
					answer.add(count);					
				}
			}
		}
		System.out.println(answer.size());
		Collections.sort(answer);
		for(int i=0; i<answer.size(); i++) System.out.println(answer.get(i));
	}
	
	public static void main(String[] args) {
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		int[][] arr = new int[n][n];
		for(int i=0; i<n; i++) {
			String s = sc.next();
			for(int j=0; j<n; j++) {
				arr[i][j] = s.charAt(j)-'0';
			}
		}
		T.solution(arr);
		sc.close();
	}
}

---

코드 설명

4방향 탐색 설정

static int[] dx = {-1, 0, 1, 0};
static int[] dy = {0, 1, 0, -1};

• 상, 우, 하, 좌 순서로 이동하기 위한 배열

---

입력 처리

n = sc.nextInt();
int[][] arr = new int[n][n];
for (int i = 0; i < n; i++) {
    String s = sc.next();
    for (int j = 0; j < n; j++) {
        arr[i][j] = s.charAt(j) - '0';
    }
}

• 각 줄을 String으로 받아서 문자 하나하나를 int로 변환
• '0'은 0, '1'은 1로 변환됨

---

BFS 탐색

if (arr[x][y] == 1) {
    arr[x][y] = 0; // 방문 처리
    q.offer(new Point(x, y));
    int count = 1;

    while (!q.isEmpty()) {
        Point tmp = q.poll();
        for (int i = 0; i < 4; i++) {
            int nx = tmp.x + dx[i];
            int ny = tmp.y + dy[i];

            if (nx >= 0 && nx < n && ny >= 0 && ny < n && arr[nx][ny] == 1) {
                arr[nx][ny] = 0;
                count++;
                q.offer(new Point(nx, ny));
            }
        }
    }

    answer.add(count);
}

• BFS를 통해 하나의 단지를 모두 탐색하며 집의 수를 셈
• 방문한 집은 0으로 마킹하여 다시 방문하지 않게 함

---

출력

System.out.println(answer.size());
Collections.sort(answer);
for (int num : answer) {
    System.out.println(num);
}

• 단지 수 출력
• 각 단지의 집 수를 오름차순으로 출력

---

시간 복잡도

• 탐색: 모든 셀을 한 번씩 확인 → O(N × N)
• 정렬: A는 단지 개수, 최악의 경우 N×N → O(A log A)
• 총 시간 복잡도: O(N² + A log A)