📌 문제 요약

• 문제 이름: 2667번: 단지번호붙이기
• 알고리즘 분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS)
• 사용 언어: Python 3

정사각형 모양의 지도가 주어집니다. 1은 집이 있는 곳, 0은 집이 없는 곳을 나타냅니다. 상하좌우로 연결된 집들을 하나의 '단지'로 묶어 번호를 붙일 때, 총 단지 수와 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 문제입니다.

💡 문제 접근 방법 (핵심 로직)

이 문제는 2차원 배열을 탐색하여 연결 요소(Connected Component) 의 개수와 각각의 크기를 구하는 전형적인 그래프 탐색 문제입니다. 한 집에서 시작해 상하좌우로 퍼져나가며 단지의 크기를 구해야 하므로 BFS(너비 우선 탐색) 를 활용했습니다.

1. 방향 벡터 설정: 2차원 지도 위에서 상, 하, 좌, 우로 이동하기 위해 dx = [-1, 1, 0, 0], dy = [0, 0, -1, 1] 배열을 만들어 활용합니다.
2. 모든 좌표 탐색: 지도 전체를 이중 for문으로 훑으며, "아직 방문하지 않았고, 집이 있는(1) 곳"을 찾습니다. 이곳이 새로운 단지의 시작점이 됩니다.
3. 단지 크기 측정 (BFS):
   • 시작점을 큐(Queue)에 넣고 방문 처리한 뒤, 큐에서 좌표를 하나씩 뽑아 상하좌우를 살핍니다.
   • 지도의 범위를 벗어나지 않으면서, 연결된 집(1)이고 미방문 상태라면 큐에 넣고 count를 1씩 증가시킵니다.
   • 탐색이 끝나면 그 단지의 총 count를 반환하여 result 리스트에 저장합니다.
4. 결과 정렬: 모든 지도를 다 살펴본 후, result 배열을 오름차순으로 정렬하여 출력합니다.

💻 코드 구현

import sys
from collections import deque

input = sys.stdin.readline

N = int(input())

graph = [list(map(int, input().strip())) for _ in range(N)]
visited = [[False] * N for _ in range(N)]

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

result = []

def bfs(start_x, start_y):
    count = 1
    queue = deque([(start_x, start_y)])
    visited[start_x][start_y] = True
    
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if (nx >= 0 and nx < N) and (ny >= 0 and ny < N):
                if graph[nx][ny] == 1 and not visited[nx][ny]:
                    queue.append((nx, ny))
                    visited[nx][ny] = True
                    count += 1
                    
    return count                     
                        
for x in range(N):
    for y in range(N):
        if graph[x][y] == 1 and not visited[x][y]:
            result.append(bfs(x, y))

result.sort()
print(len(result))
for i in range(len(result)):
    print(result[i])

🚨 트러블 슈팅 및 회고

• 문자열 입력 파싱의 주의점: 기존 그래프 문제들처럼 map(int, input().split())을 사용하려고 했으나, 이 문제는 입력이 0110100 처럼 공백 없이 붙어있습니다. 이럴 때는 sys.stdin.readline의 경우 문자열 끝에 줄바꿈 문자(\n)가 포함되므로 strip()으로 공백을 제거한 후, list(map(int, ...))로 묶어주어야 1자리 정수 단위의 리스트로 예쁘게 쪼개진다는 파이썬만의 문자열 처리 팁을 복습할 수 있었습니다.
• 방향 벡터(dx, dy) 테크닉: $x, y$ 좌표를 다룰 때 단순히 if문 4개를 나열하는 것보다, dx, dy 리스트와 for문을 조합하면 코드가 훨씬 간결해지고 유지보수(예: 대각선 방향이 추가될 경우)가 쉬워진다는 점을 체감했습니다. 이 구조는 다른 시뮬레이션 문제나 DFS/BFS 문제에서도 일종의 템플릿처럼 유용하게 쓰일 것 같습니다.