문제 출처 : https://www.acmicpc.net/problem/2667
난이도 : 실버 1

문제 파악

N x N 격자에서

• 1 = 집
• 0 = 빈 칸

상하좌우로 연결된 집(1)들은 같은 “단지”로 묶인다.

출력해야 하는 것:
1) 단지 개수
2) 각 단지에 속한 집의 수(크기)를 오름차순으로 출력

한칸의 셀에서 상하좌우로 탐색하며 연결되어있는 지 파악하고 연결된 요소들의 길이를 저장해야 한다.

해결 아이디어

1. 격자의 모든 칸을 (0,0)부터 끝까지 훑는다.
2. 어떤 칸이 1이고 아직 방문하지 않았다면:
   • 여기서 새로운 단지가 시작된 것이다.
   • BFS(또는 DFS)를 시작해서 연결된 1을 전부 방문 처리한다.
   • 방문한 칸 수를 세면 그 단지의 크기가 된다.
3. 모든 칸을 다 훑으면:
   • 단지 크기 리스트의 길이 = 단지 개수
   • 단지 크기 리스트를 정렬해서 출력한다.

N의 최대는 25이기에 O(N^2)로 풀이가 가능하다.

해답 및 풀이

from collections import deque
import sys
input = sys.stdin.readline

N = int(input())

graph = []
for _ in range(N):    
    graph.append(list(map(int, input().strip())))  

# 상, 하, 좌, 우 를 탐색해야 한다? -> 방향벡터 정의
# dx[0],dy[0] = 상, dx[1],dy[1] = 하, dx[2],dy[2] = 좌, dx[3],dy[3] = 우
dx = [-1,1,0,0]
dy = [0,0,-1,1]

def bfs(x,y): # x,y에서 스타트해서 bfs 탐색
    queue = deque()
    queue.append((x,y))
    
    graph[x][y] = 0 # 탐색한 위치를 0으로 바꾸어 다시 방문하지 않게끔 처리
    count = 1

    while queue: # 큐가 빌때까지 반복
        x, y = queue.popleft()

        # x,y의 상하좌우 탐색
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]

            if 0 <= nx < N and 0 <= ny < N and graph[nx][ny] == 1: # 탐색하려는 좌표 nx,ny 가 범위내에 존재하고 그 값이 1이라면
                graph[nx][ny] = 0 # 0으로 방문 처리
                queue.append((nx,ny))
                count += 1
    return count


result = []
for i in range(N):
    for j in range(N):
        if graph[i][j] == 1: # graph를 완전탐색하며 1인 값을 찾는 순간
            result.append(bfs(i,j)) # bfs 돌면서 그 1과 상하좌우로 연결된 값들을 0으로 바꿔버리며 count 증가.

print(len(result))
for r in sorted(result):
    print(r)