[백준] 2583 영역구하기

www.acmicpc.net/problem/2583

2583번: 영역 구하기

from collections import deque


def bfs(row, col):
    q = deque()
    dr = [-1, 1, 0, 0]
    dc = [0, 0, -1, 1]
    q.append((row, col))
    matrix[row][col] = 1
    while q:
        nr, nc = q.popleft()
        for i in range(4):
            if 0 <= nr + dr[i] < m and 0 <= nc + dc[i] < n:
                if matrix[nr + dr[i]][nc + dc[i]] == 1: continue
                q.append((nr + dr[i], nc + dc[i]))
                matrix[nr + dr[i]][nc + dc[i]] = 1
                global area
                area += 1


m, n, k = map(int, input().split())
matrix = [[0] * n for _ in range(m)]
for _ in range(k):
    # r= 4, c = 6
    ld_c, ld_r, ru_c, ru_r = map(int, input().split())
    for r in range(ld_r, ru_r):
        for c in range(ld_c, ru_c):
            matrix[r][c] = 1
cnt, area = 0, 0
area_list = []

for i in range(m):
    for j in range(n):
        if matrix[i][j] == 0:
            cnt += 1
            area = 1
            bfs(i, j)
            area_list.append(area)
print(cnt)
print(*sorted(area_list))

스터디하면서 한시간 정도에 두 문제 풀기로 했고, 그 문제 중 하나이다.

이전부터 해왔던 문제들을 합친 문제이다. 종이 겹치기랑 단지 번호 구하기 였나?

배열을 만들고 겹칠때 좀 헷갈렸지만 그냥저냥 하다보니 풀렸다.

번호를 구하기 위해서 dfs로 할지 bfs로 할지 고민하다가 손에 익힐겸 bfs로 했다.