boj 2583 (실버1)

문제

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

오랜만에 백준문제 하나 풀어보았다.
그냥 BFS, DFS 한번 해보고싶어서 카테고리 들어가서 아무거나 하나 골랐다

왼쪽 아래부분을 0,0으로 주어서 좌표계가 헷갈렸는데
어차피 넓이를 구하는것이니 그림이랑 똑같이 좌표로 구현할 필요는 없을것 같아서
왼쪽 위가 0,0이다 생각하고 일관되게만 처리했다.

90도 돌아간 그림일것이다
하지만 그림을 돌린다고 해도 넓이가 바뀌는것은 아니니 그냥 요렇게 풀었따

쉬운 문제라 별다른 특이한 아이디어는 없는것같다.

풀이

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

arr = [[False] * m for _ in range(n)]

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


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

def dfs(a,b):
  q = []
  count = 1
  arr[a][b] = True
  q.append((a,b))
  while(q):
    y,x = q.pop()
    for i in range(4):
      ny = y + dy[i]
      nx = x + dx[i]

      if 0 <= ny < n and 0 <= nx < m and arr[ny][nx] == False:
        arr[ny][nx] = True
        q.append((ny,nx))
        count += 1

  return count
    
    
answer = []

for i in range(n):
  for j in range(m):
    if arr[i][j] == False:
      answer.append(dfs(i,j))

print(len(answer))
for i in sorted(answer):
  print(i,end = ' ')

결과