2583

날짜 : 2023. 02. 09

사용 언어 : python

 

문제

 

 

코드

import sys
from collections import deque

m, n, k = map(int, sys.stdin.readline().split())  # 열, 행, 테스트케이스
g = [[0] * m for i in range(n)]  # 빈 그래프(0으로 초기화)

for _ in range(k):
    x1, y1, x2, y2 = map(int, sys.stdin.readline().split())  # x, y값 입력
    for i in range(x1, x2):
        for j in range(y1, y2):
            g[i][j] = 1  # 색칠

def bfs(r, c):
    w = 1
    queue = deque()
    queue.append([r, c])
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]

    while queue:
        row, col = queue.popleft()
        for i in range(4):
            x = row + dx[i]
            y = col + dy[i]
            if x in range(n) and y in range(m): # 범위에 있는 경우
                if g[x][y] == 0: # 방문하지 않은 경우
                    g[x][y] = 2 # 방문처리
                    w += 1
                    queue.append([x, y])
    return w

cnt = 0  # 비어있는 영역 개수
res = list()
for i in range(n):
    for j in range(m):
        if g[i][j] == 0:  # 비어있는 영역
            g[i][j] = 2 # 방문처리
            cnt += 1
            wid = 0
            res.append(bfs(i, j))  # 넓이 출력

# for i in g: print(i)
res.sort()
print(cnt)
for i in res: print(i, end=" ")

 

 

풀이

- 수학에서의 함수 좌표처럼 x, y값을 제공하기 때문에 그에 맞게 입력받은 후 BFS를 이용하여 답을 구한다.

 

 

알게된 점

- x, y값의 입력이 조금 헷갈리긴 했지만 태블릿에 그려서 푸니까 곧바로 해결됐다.

- 그 다음은 단순하게 BFS를 활용해서 풀이하는 문제였다.

 

 

참고 사이트

-