[백준][Python] 2667번 단지번호붙이기

DFS 풀이

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

def dfs(x,y):
    
    if x <= -1 or x >= n or y <= -1 or y >= n:
        return False
    
    if matrix[x][y] == 1:
        global nums
        matrix[x][y] = 0
        nums += 1
        
        dfs(x - 1, y)
        dfs(x, y - 1)
        dfs(x + 1, y)
        dfs(x, y + 1)
        return True
    return False

result = 0
nums = 0
numlist = []
for i in range(n):
    for j in range(n):
        if dfs(i,j) == True:
            result += 1
            numlist.append(nums)
            nums = 0
print(result)
numlist.sort()
for i in numlist:
    print(i)

BFS 풀이

from collections import deque    

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

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

def bfs(x,y):
    
    queue = deque()
    queue.append((x,y))
    graph[x][y] = 0
    count = 1
    while queue:
        x,y = queue.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] == 0:
                continue
            if graph[nx][ny] == 1:
                graph[nx][ny] = 0
                queue.append((nx,ny))
                count += 1
    return count

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

cnt.sort()
print(len(cnt))
for i in cnt:
    print(i)