/ ALGORITHM

백준 - 단지번호붙이기(#2667)

백준 2667번

image-20230121203114811

#BFS를 이용한 풀이
from collections import deque
import sys
input = sys.stdin.readline

N = int(input())
maps = [list(map(int,input().strip())) for _ in range(N)]
visited=[[0]*N for _ in range(N)]
answer=[]

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

def bfs(i,j):
    queue = deque([[i,j]])
    count=1
    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx,ny=x+dx[i],y+dy[i]

            if nx<0 or ny<0 or nx>N-1 or ny>N-1:
                continue
            
            if not visited[nx][ny]:
                if maps[nx][ny]==1:
                    visited[nx][ny]=1
                    count+=1
                    queue.append([nx,ny])
    return count

for i in range(N):
    for j in range(N):
        if not visited[i][j]:
            if maps[i][j]==1:
                visited[i][j]=1
                answer.append(bfs(i,j))

answer.sort()
print(len(answer))
for i in answer:
    print(i)
#DFS를 이용한 풀이
import sys
input = sys.stdin.readline

N = int(input())
maps = [list(map(int,input().strip())) for _ in range(N)]
visited = [[False]*N for _ in range(N)]
answer=[]
dx=[1,-1,0,0]
dy=[0,0,1,-1]

def dfs(x,y):
    global count
    for i in range(4):
        nx,ny=x+dx[i],y+dy[i]
        if nx<0 or ny<0 or nx>N-1 or ny>N-1:
            continue
        if not visited[nx][ny]:
            if maps[nx][ny]==1:
                count+=1
                visited[nx][ny]=True
                dfs(nx,ny)

for i in range(N):
    for j in range(N):
        if not visited[i][j]:
            if maps[i][j]==1:
                visited[i][j]=True
                count=1
                dfs(i,j)
                answer.append(count)
answer.sort()
print(len(answer))
for i in answer:
    print(i)