문제
눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다.
예를 들어 M=5, N=7 인 모눈종이 위에 <그림 1>과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 <그림 2>와 같이 3개의 분리된 영역으로 나누어지게 된다.
<그림 2>와 같이 분리된 세 영역의 넓이는 각각 1, 7, 13이 된다.
M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작성하시오.
풀이
이 문제에서 주의깊게 봐야할 부분은 테이블이 뒤집어져 있다는 점이라고 할 수 있지만 이 문제는 위 아래가 중요한 문제는 아니기 때문에 0,0이 아래고 마지막점이 위인건 신경쓰지 않고 영역만 구해주면 된다.
또한 이렇게 거꾸로 구할 때에는 입력에서 주어진 row, column 값이 반대로 주어지기 때문에 이것만 유의하면 된다.
c1, r1, c2, r2 = map(int, input().split()) 이 코드와 같이 row와 column을 뒤집어서 받아주고 이 row column에 해당하는 수는 영역의 밖이기 때문에 이중 for문을 돌아 모두 1로 초기화 해준다.
마지막으로 전체 그래프를 순회하면서 i,j의 값이 0이고 방문한 적이 없다면 bfs를 실행하고 그 리턴값을 정답리스트에 담고 정렬해서 출력해주면 된다.
from collections import deque
import sys
input = sys.stdin.readline
N, M, K = map(int, input().split())
graph = [[0] * M for _ in range(N)]
visited = [[0] * M for _ in range(N)]
directions = [[0, 1], [1, 0], [-1, 0], [0, -1]]
for _ in range(K):
c1, r1, c2, r2 = map(int, input().split())
for i in range(r1,r2):
for j in range(c1, c2):
if graph[i][j] == 1: continue
graph[i][j] = 1
def get_white_area(row:int, column:int) -> int:
queue = deque()
queue.append((row, column))
visited[row][column] = 1
area = 1
while queue:
cur_row, cur_col = queue.popleft()
for direction in directions:
next_row = cur_row + direction[0]
next_col = cur_col + direction[1]
if next_row < 0 or next_row >= N or next_col <0 or next_col >=M: continue
if visited[next_row][next_col]: continue
if graph[next_row][next_col] == 1:continue
visited[next_row][next_col] = 1
queue.append((next_row, next_col))
area +=1
return area
answer = []
for i in range(N):
for j in range(M):
if graph[i][j] == 0 and not visited[i][j]:
answer.append(get_white_area(i, j))
print(len(answer))
print(*sorted(answer))