[백준][Python] 2583번 영역 구하기

BFS 풀이

from collections import deque

def bfs(x,y):
    
    queue = deque()
    queue.append((x,y))
    graph[x][y] = 1
    result = 1
    
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    
    while queue:
        
        x,y = queue.popleft()
        
        for i in range(len(dx)):
            
            nx = x + dx[i]
            ny = y + dy[i]
            
            if nx <= -1 or nx >= m or ny <= -1 or ny >= n:
                continue
            if graph[nx][ny] == 1:
                continue
            if graph[nx][ny] == 0 :
                
                queue.append((nx,ny))
                graph[nx][ny] = 1
                result += 1
    return result
            
graph = []
m,n,k = map(int,input().split())
x_graph = []
y_graph = []
for i in range(k):
    matrix = list(map(int,input().split()))
    x_graph.append(matrix[::2])
    y_graph.append(matrix[1::2])
    for j in range(2):
        
        y_graph[i][j] = m - y_graph[i][j]
    
    y_graph[i][0],y_graph[i][1] = y_graph[i][1],y_graph[i][0]
graph = [[0] * n for i in range(m)]
for index in zip(y_graph,x_graph):
    x_index = index[0]
    y_index = index[1]
    for i in range(x_index[0],x_index[1]):
        for j in range(y_index[0],y_index[1]):
            graph[i][j] = 1

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

cnt.sort()
print(len(cnt))
for i in cnt:
    print(i, end = " ")

DFS 풀이

import sys
sys.setrecursionlimit(10000)

def dfs(x,y):
    
    global result 
    visited[x][y] = 1
    result += 1
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    
    for i in range(len(dx)):
        
        nx = x + dx[i]
        ny = y + dy[i]
        
        if 0 <= nx < m and 0 <= ny < n :
            
            if graph[nx][ny] == 0 and visited[nx][ny] == 0:
                
                dfs(nx,ny)

graph = []
m,n,k = map(int,input().split())
x_graph = []
y_graph = []
for i in range(k):
    matrix = list(map(int,input().split()))
    x_graph.append(matrix[::2])
    y_graph.append(matrix[1::2])
    for j in range(2):
        
        y_graph[i][j] = m - y_graph[i][j]
    
    y_graph[i][0],y_graph[i][1] = y_graph[i][1],y_graph[i][0]
graph = [[0] * n for i in range(m)]
for index in zip(y_graph,x_graph):
    x_index = index[0]
    y_index = index[1]
    for i in range(x_index[0],x_index[1]):
        for j in range(y_index[0],y_index[1]):
            graph[i][j] = 1
visited = [[0] * n for i in range(m)]        

result = 0
cnt = []
for i in range(m):
    for j in range(n):
        
        if graph[i][j] == 0 and visited[i][j] == 0 :
            
            dfs(i,j)
            cnt.append(result)
            result = 0
            
cnt.sort()   
print(len(cnt))   
for i in cnt:
    print(i, end =" ")