<dfs, bfs> 백준 2583번. 영역 구하기 (실버 1)

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

2583번: 영역 구하기

from collections import deque


m,n,k = map(int, input().split())
lst = [[0]*n for _ in range(m)]
visited = [[0]*n for _ in range(m)] #방문처리
dx = [0, 0, 1, -1]
dy = [1, -1, 0 , 0]

# print(lst)
for _ in range(k):
  y1, x1, y2, x2 = map(int, input().split())
  # print("전: (x1,y1)", x1, y1," (x2,y2)", x2, y2)
  x1 = m - x1
  x2 = m - x2
  # print("후: (x1,y1)", x1, y1," (x2,y2)", x2, y2)
  for i in range(len(lst)):
    for j in range(len(lst[i])):
      if x2<=i<x1 and y1<=j<y2 :
        lst[i][j] = 1


def bfs(lst, x, y):   
  q = deque()
  q.append((x,y)) #큐에 추가
  cnt = 1  
  lst[x][y] = True #방문처리
  while q:
    x,y = q.popleft()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if 0<=nx<m and 0<=ny<n :
        if lst[nx][ny] == False:
          lst[nx][ny] = True
          q.append((nx,ny))
          cnt += 1
  return cnt

result = []
for i in range(m):
    for j in range(n):
        if lst[i][j] == False: #방문하지 않았다면
            result.append(bfs(lst, i, j))

result.sort()
print(len(result))
print(*result, sep=' ')   
  
"""
5 7 3
0 2 4 4
1 1 2 5
4 0 6 2

"""

맵을 아래부터 (0,0)으로 세서 조금 헤맸다.

그림을 그려가며 이해했는데, 코테에선 종이를 못 쓰니깐 걱정이다

그리고 오랜만에 bfs를 푸니까 까먹어서 알고리즘 코드를 참고하였음 ㅠ