[ 백준 / 파이썬 ] 2583. 영역 구하기

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

2583번: 영역 구하기

🎉🎉 문제

눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다.

M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작성하시오.

 

 

🎉🎉 풀이

✅ 직사각형이 어디에 있는지 표시된 2차원 배열을 만든다

✅ 2차원 배열을 돌면서 빈 공간을 dfs로 탐색해 넓이와 영역의 개수를 구한다

✅ 출력할 때 *sorted(list) 하면 리스트 원소들을 공백을 두고 출력해주는 듯

 

 

🎉🎉 코드

import sys
sys.setrecursionlimit(10**6)

def dfs(i, j, n, m):
  global cnt
  visited[i][j] = True
  cnt += 1 #넓이 1칸 추가

  #상우하좌
  di = [-1, 0, 1, 0]
  dj = [0, 1, 0, -1]

  for k in range(4):
    ni = i+di[k]
    nj = j+dj[k]

    if 0<=ni<n and 0<=nj<m:
      if not visited[ni][nj] and graph[ni][nj] == 0: #아직 방문 안 한 곳이면서 비어있는 영역이면
        dfs(ni, nj, n, m) #탐색하러 들어간다

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

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

for _ in range(k):
  x1, y1, x2, y2 = map(int, input().split()) #직사각형 왼쪽 아래 모서리와 오른쪽 위 모서리의 좌표
  for i in range(y1, y2):
    for j in range(x1, x2):
      graph[i][j] = 1 #직사각형 표시


visited = [[False]*m for _ in range(n)] #방문처리

answer = [] #넓이 담을 배열
ground = 0 #영역의 개수
global cnt
for i in range(n):
  for j in range(m):
    cnt = 0
    if not visited[i][j] and graph[i][j] == 0:
      dfs(i, j, n, m)
      answer.append(cnt) #카운트 한 넓이를 기록
      ground += 1 #영역의 개수 추가


print(ground)
print(*sorted(answer)) #오름차순 정렬해서 출력