백준 2583번 영역구하기 python 파이썬

문제를 처음 보고 든 생각은 백준의 안전영역구하기 문제와 굉장히 유사하다는 느낌을 받았다.

특정영역에 대해서 처리를 해주고 그 크기를 주해주는 점에서 bfs 알고리즘을 사용해서 처리해주면 될 것같다고 판단하였다.

그런데 이 문제의 가장 어려운 점이라고 하면 평상시 풀던 좌표 문제와는 x, y축이 예제와 다르다는 것이다

그래서 나는 주어진 x1,y1,x2,y2 좌표를 반대로 받아서 처리해주었다.

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

#비어있는 좌표판을 만들어줌
background = [[0]*n for _ in range(m)]

klist=[]
for _ in range(k):
   y1,x1,y2,x2 = map(int, input().split())
   #사각형이 그려지는 부분 체크 해줌
   for i in range(x1,x2):
    for j in range(y1,y2):
      background[i][j] = 1  
#print(background)

from collections import deque
ans = []

def bfs(a,b):
  q = deque()
  dx = [-1,1,0,0]
  dy = [0,0,-1,1]
  q.append((a,b))
  background[a][b] =1
  cnt = 1
  while(q):
    x,y = q.popleft()
    
    for i in range(4):
      nx = dx[i] + x
      ny = dy[i] + y
      if 0<= nx <m and 0<= ny <n and background[nx][ny] == 0:
        background[nx][ny] = 1
        q.append((nx,ny))
        cnt+=1
  ans.append(cnt)



for i in range(m):
  for j in range(n):
    if background[i][j]==0:
      bfs(i,j)
      

print(len(ans))
ans.sort()
for a in ans:
  print(f'{a} ', end='')

예제의 x,y좌표와 2차원배열에서의 x,y좌표가 다르다는 점을 잘 생각해서 변형시켜적용해주는 점이 가장 어려웠던 문제였던 것 같다