2583번 - 영역 구하기

💡 bfs 중 시작하자마자 종료되는 조건을 잘 헤아려야 하는 문제

import sys
from collections import deque

input = sys.stdin.readline

M, N, K = map(int, input().rstrip().split(' '))

graph = [[0] * N for _ in range(M)]
total_square = []
cnt = 0

def bfs(x,y):
    
    dq = deque()
    dq.append((x,y))
    graph[y][x] = 1
    square = 1
    
    #상하좌우
    dx = [0,0,-1,1]
    dy = [1,-1,0,0]
    
    while dq:
        x, y = dq.popleft()
        for idx in range(4):
            nx = x + dx[idx]
            ny = y + dy[idx]
            if 0 <= nx < N and 0 <= ny < M and graph[ny][nx] == 0:
                graph[ny][nx] = 1
                dq.append((nx,ny))
                square += 1
    
    return square

for _ in range(K):
    
    left_x , left_y, right_x, right_y = map(int, input().rstrip().split(' '))
    
    # 사각형 해당 영역 먼저 넣기
    for i in range(left_y, right_y):
        for j in range(left_x, right_x):
            graph[i][j] = -1

# bfs 넣기        
for y in range(M):
    for x in range(N):
        if graph[y][x] == 0:
            total_square.append(bfs(x,y))
            cnt += 1

print(cnt)
print(' '.join(map(str,sorted(total_square))))

• bfs문제를 많이 풀어봤지만, 늘 느끼는거는 각 문제들마다 bfs이지만 접근법이 조금씩은 다 다르다는 것이다.
• 이 문제에서의 차이점은 우리가 벽의 범주에 해당하는 입력값을 받아서 벽을 만들어야된다는 점이다.
  먼저 벽을 전부 만들고 나서, bfs를 돌려주는 방식으로 진행하였고, 결과값 자체가 이동가능한 영역의 갯수와 각 영역의 넓이를 구해야 했기 때문에, bfs에 들어갈때마다 cnt를 +1 해주고, bfs 내부에서도 영역의 넓이값을 계산해줘야 했다.
• 문제를 풀면서 만났던 문제는 어떻게 영억의 넓이를 구할 것인가와 들어가자마자 벽을 만났을 때가 문제였다.
  이 문제는 특정 지점에 도달하는 최솟값을 구하는것이 아니였기 떄문에, 순회하면서 dq에 들어갈때 square에 1을 더해 총 영역의 넓이를 계산하였다.
  또한 들어가자마자 벽을 만날 경우를 대비하여, 처음 입장시부터 입력받은 시작점 값을 계산해주는 방식으로 해결하였다.