백준 2667번 파이썬 bfs, dfs

bfs

from collections import deque

n= int(input())

board= []

cnt=0

cntarr=[]

for i in range(n):

  

    board.append(list(map(int, input())))

def bfs(graph,x,y):

  

    global cnt

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

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

    queue=deque()

    queue.append((x,y))

    cnt=1

    while queue:

        x,y=queue.popleft()

        graph[x][y]=0

        

      

        for j in range(4):

            nx=x+dx[j]

            ny=y+dy[j]

            if nx<0 or nx>=n or ny<0 or ny>=n:

                continue

            if graph[nx][ny]==1:

                graph[nx][ny]=0

                queue.append((nx,ny))

                cnt+=1

    return cnt

for p in range(n):

    for q in range(n):

        if board[p][q]==1:

            

            cntarr.append(bfs(board,p,q))

            

cntarr.sort()

print(len(cntarr))

for qw in range(len(cntarr)):

    print(cntarr[qw])

 

dfs

n=int(input())

arr=[]

board=[]

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

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

for _ in range(n):

    board.append(list(map(int,input())))

def dfs(x,y):

    global cnt

    if x<0 or x>=n or y<0 or y>=n:

        return False

    if board[x][y]:

        

        board[x][y]=0

        cnt+=1

        for i in range(4):

            nx=x+dx[i]

            ny=y+dy[i]

            dfs(nx,ny)

        return True

    return False

cnt=0

res=0

for p in range(n):

    for q in range(n):

        if dfs(p,q):

            res+=1

            arr.append(cnt)

            cnt=0

          

arr.sort()

print(res)

for t in range(len(arr)):

    print(arr[t])