👩‍🎓공부 - 2023.12.28 오늘의 백준 문제풀이

2583번 - 영역 구하기

그림과 같이 도화지 위에 직사각형의 집합이 주어지면 직사각형을 제외한 영역의 개수와 넓이를 구하는 문제입니다.

que = deque()
amount = []
M,N,K = map(int,input().split())
graph = [[0]*N for _ in range(M)]
for _ in range(K):
    a,b,c,d = map(int,input().split())
    for i in range(b,d):
        for j in range(a,c):
            graph[i][j] = 1

BFS를 사용하기 위해 que를 받아오고 그래프를 이차원 리스트 위에 표현하기 위해 a,b,c,d 변수를 받은 다음 for문을 통해 직사각형이 그려진 위 도화지를 구현해줍시다.

출력 자체는 위 도화지 케이스랑 상하좌우 반전을 시킨 값으로 나오는데 결과적으로 값이나 주어진 공간의 넓이 직사각형의 넓이 등 구하는 데는 지장이 없으니까 진행해도 됩니다.

sum = 0
for m in range(M):
    for n in range(N):
        if graph[m][n] == 0:
            graph[m][n] = 2
            amount.append(bfs(m,n)+1)
            sum += 1

도화지 위에 직사각형이 아닌 빈공간은 2로 표기해주도록 하겠습니다. 탐색이 안된 빈공간의 초기값은 0이므로 0일때 탐색을 시작하는 자기자신을 2로 설정하고 BFS 함수를 돌립니다.

from collections import deque
dx = [-1,1,0,0]
dy = [0,0,1,-1]

def bfs(x,y):
    a = 0
    que.append([x,y])
    while que:
        x,y = que.popleft()
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y
            if nx<0 or ny<0 or nx>=M or ny>=N:
                continue 
            if graph[nx][ny] == 0:
                graph[nx][ny] = 2
                a += 1
                que.append([nx,ny])
    return a

항상 하던 것처럼 4방향 탐색을 실시하는 중에 만약 4방향 중에서 탐색이 안된 빈공간 0을 만나면 2로 바꿔주고 빈공간의 넓이를 구하기 위해 해당 공간을 만날때마다 a값에 1을 더해줍니다. 최종적으로는 빈공간의 넓이를 리턴해줍니다.

            amount.append(bfs(m,n)+1)
            sum += 1

아까 위에 탐색시작 for문 안에 이런게 적혀있었는데 넓이를 구하는 식은 자기 자신을 제외시키고 탐색을 하므로 1을 추가시킨 넓이값을 amount 배열에 추가시키고 bfs가 끝났으면 최종적으로 그 구역 탐색은 종료된 것이므로 직사각형이 아닌 공간의 개수 + 1을 해줍니다.

amount.sort()
print(sum)
for values in amount:
    print(values,end=' ')

마지막으로 amount를 정렬하고 sum값과 amount 값을 출력하면 답이 나옵니다.