<dfs bfs>백준 2667번. 단지번호붙이기

 

from collections import deque
import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline


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

n = int(input())
graph = [ list(map(str, input())) for _ in range(n) ]

def bfs(x,y):
  cnt = 1
  q = deque()
  q.append( (x,y) )
  graph[x][y] = 0
  while q:
    
    x, y = q.popleft()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if 0<=nx<n and 0<=ny<n:
        if graph[nx][ny] == "1": #집이 있으면
          q.append((nx,ny))
          graph[nx][ny] = 0
          cnt += 1
  cnt_lst.append(cnt)    

for i in range(n):
  for j in range(n):
    if graph[i][j] == "1" : #집이 있으면
      bfs(i,j)
print(len(cnt_lst))
cnt_lst.sort()
print(*cnt_lst, sep = "\n")

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

2667번: 단지번호붙이기