백준 알고리즘 2667번

백준링크

sys 라이브러리를 사용할때는 한 줄 입력받고 rstrip()을 꼭 호출

readline은 \n도 받으므로, 이 공백문자를 제거하는 역할을 한다.

파이썬

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

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

def bfs(graph,a,b):
    n = len(graph)
    q = deque()
    q.append((a,b))
    graph[a][b] = 0
    count = 1
    
    while q:
        x,y = q.popleft()
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= n:
                continue
            if graph[nx][ny] == 1:
                graph[nx][ny] = 0
                q.append((nx,ny))
                count += 1
    return count
    

n = int(input())
graph=[]
for i in range(n):
    graph.append(list(map(int,input().rstrip())))

cnt = []
for i in range(n):
    for j in range(n):
        if graph[i][j] == 1:
            cnt.append(bfs(graph,i,j))
            
cnt.sort()
print(len(cnt))
for i in range(len(cnt)):
    print(cnt[i])