[Python] 백준 알고리즘 2583번: 영역 구하기

이번에 푸는 문제는 백준 알고리즘 2583번: 영역 구하기로 난이도는 Siver 1 에 해당한다.

문제는 다음과 같다.

이문제도 이전 4693번과 마찬가지로 2667번 단지번호 붙이기와 유사하다.

 

단지번호 붙이기 문제에서는 그래프 G를 0과 1로 표현하여 인접해있는 사각형을 제시한다. 이번문제에서는 사각형을 제시하는 방법이 달랐을 뿐, 풀이방법은 2667번과 거의 똑같다.

 

# 작성자 : SH_WON_96
# # 2021-01-07
# # 알고리즘 - Graph
# # 문제번호 : 2583 영역 구하기
#
# # 초기 입력값 받기
import sys
from collections import deque
input = sys.stdin.readline
queue = deque()
input = sys.stdin.readline
N,M,K = map(int, input().split(" "))

# N 행 M 열
# 그래프 생성
G = [[1 for i in range(M)] for i in range(N)]

# 좌표값에 맞는 직사각형 만들기 (주어진 그림과 똑같게 나타냈는데, 그럴 필요는 없음)
for i in range(K):
    x1,y1,x2,y2 = list(map(int, input().strip().split(" ")))
    #x1 ~ x2, y1 ~ y2 에 해당하는 G를 0으로 변경
    for t in range(x2-x1):
        for k in range(y2-y1):
            G[N-1-(y1+k)][x1+t] = 0

# 직사각형 체크
# for i in range(len(G)):
#     print(G[i])


# 블록 찾기시작
howmany =[] # 직사각형 넓이 리스트


dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
visited = [[0 for i in range(M)] for _ in range(N)]

# 방문했으면 visited를 1로 바꿈, DFS로 최대 내려갈 수 있는 깊이 count
def findblock(queue, visited):
    count = 0
    while queue:
        x, y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if (0 <= nx < N) and (0 <= ny < M):
                if (visited[nx][ny] == 0 and G[nx][ny] == 1):
                    visited[nx][ny] = 1
                    queue.append((nx, ny))
                    count += 1
    return count


# 직사각형이 존재하는 구역들 중 방문하지 않은 구역들 확인하면서 DFS 들어감
for i in range(N):
    for j in range(M):
        if G[i][j] == 1 and visited[i][j]==0:
            queue.append((i,j))
            howmany.append(findblock(queue, visited))


howmany.sort()
print(len(howmany))
for i in range(len(howmany)):
    if howmany[i] == 0:
        print(1,end=" ")
    else:
        print(howmany[i],end=" ")

---

문제는 아래 ↓링크↓

2583번: 영역 구하기