[백준/Python] 2583번: 영역 구하기

📁 문제

https://www.acmicpc.net/problem/2583

---

💭 풀이

① 눈금의 간격이 1인 MxN 크기의 모눈종이
② 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때
③ 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어짐
❗ K개의 직사각형들이 모눈종이 전체를 채우는 일 X

📍 분리된 영역의 개수, 분리된 각 영역의 넓이 출력

---

🍰 알고리즘

1) 2차원 배열 생성 → 직사각형 영역 = 1, 나머지 부분 = 0

2) 나머지 영역 찾기 → BFS로 0인 곳 탐색

3) 상, 하, 좌, 우로 탐색하면서 넓이 1증가 (cnt +=1)

4) 탐색 끝 → 넓이를 리스트에 추가

5) 리스트를 오름차순으로 정렬

📍 리스트의 길이 = 분리된 영역의 개수
📍 리스트 내용 = 분리된 각 영역의 넓이

---

🤍 코드

from collections import deque

m, n, k = list(map(int, input().split()))

dist = [[0] * n for _ in range(m)]

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

q = deque()

for _ in range(k):
  x1, y1, x2, y2 = map(int, input().split())
  for i in range(y1, y2):
    for j in range(x1, x2):
      dist[i][j] = 1

area = []
for i in range(m):
  for j in range(n):
    if dist[i][j] == 0:
      dist[i][j] = 1
      q.append([i, j])
      cnt = 1
      
      while q:  # bfs 탐색
        y, x = q.popleft()
        for k in range(4):
          nx = x + dx[k]          
          ny = y + dy[k]
          if 0 <= ny < m and 0 <= nx < n and dist[ny][nx] == 0:
            dist[ny][nx] = 1
            q.appendleft([ny, nx])
            cnt += 1
      area.append(cnt)

area.sort()
print(len(area))
print(' '.join(map(str, area)))

• 좌표가 너무 헷갈려서 8번만에 성공
• 중첩 반복문에서는 변수를 다 다르게 지정해주어야 하는데
  같은 변수로 지정해버려서 계속 오류가 났다,,ㅠ