[백준] 2583번 - 영역 구하기 (파이썬)

백준 2583번 영역 구하기 문제

 

 

영역 구하기 문제는 빈 공간의 넓이와 갯수를 계산하여 출력하는 문제이다.

 

이번 문제는 BFS를 사용하면 간단히 해결할 수 있을 것 같아 BFS방식을 채택하여 해결하였다.

 

 

"💡 문제 해결 아이디어 "

 

벽과 벽이 아닌 곳의 구분을 하기 위해 벽:1, 벽이 아닌 곳:0으로 구현하기로 정하고 문제 해결에 들어갔다.

 

우선 입력받은 가로, 세로의 길이를 통해 높이가 M, 너비가 N인 직사각형을 만든다.

반복문을 통한 2차원 배열 생성 방식으로 그래프를 생성하였고 각 1차원 배열의 값은 모두 0으로 채운다.

그럼

[[0,0,0,0,0,0],

[0,0,0,0,0,0],

...]

과 같은 형태의 그래프가 그려진다.

 

그 다음 좌표 x1,y1,x2,y2값을 K번 입력받는데, 입력 받을 때마다 좌표값을 사용한 2중 반복문을 통해 해당되는 좌표의 0을 1로 변경하여 예시와 같은 그래프를 만들어낸다..

 

예시 그림대로 그래프가 완성되면 m,n 값을 사용한 이중 반복문으로 0,0 ~ m-1,n-1 까지 모든 곳을 돌며 graph[x][y]의 값이 0인 곳을 탐색한다.

만약 0인 곳을 발견하면 cnt를 1 증가시키고 해당 부분을 bfs로 해당 좌표의 상하좌우를 돌며 넓이를 카운트하며 그래프의 값인 0을 1로 변경한다. 이렇게 되면 탐색을 마친 곳의 값들은 모두 1로 바뀌어 탐색 대상에서 제외되고 결론적으로 모든 빈 공간의 넓이와 갯수를 구할 수 있다.

 

결과값 출력 시에는 넓이값이 오름차순으로 정렬되어야 하기 때문에 sort() 함수를 사용한 뒤, 대괄호([,])를 제외한 리스트의 값만 출력하기 위해 *result 형태로 리스트를 출력해준다.

 

코드

from collections import deque

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

m,n,k = map(int,input().split())
graph = []
for _ in range(m):
    graph.append([0 for _ in range(n)])

for _ in range(k):
    x1,y1,x2,y2 = map(int,input().split())
    for y in range(y1,y2):
        for x in range(x1,x2):
            graph[y][x] = 1

cnt = 0
result = []
for i in range(m):
    for j in range(n):
        if graph[i][j] == 0:
            cnt+=1
            result.append(bfs(i,j))
print(cnt)
result.sort()
print(*result)