#263 백준 파이썬 [2583] 영역 구하기 - BFS

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

 

Solution

1) M,N paper 배열을 만들어준 뒤, 직사각형에 해당하는 부분만 1로 바꾸어준다. 색종이 문제 https://claude-u.tistory.com/299 참고.

2) BFS 너비우선 탐색을 이용해서 직사각형에 해당하지 않는 부분 부분의 크기를 탐색해준다.

3) 함수에서는 block의 크기만 필요함으로 len(block)을 return해준다.

4) 이후 0,0부터 M,N까지 이중 for문을 돌려 BFS함수를 실행해준다.

 

Python Code

#블록이 몇개인지 알아내기 위한 BFS 너비 우선 탐색 함수를 정의
def bfs(i, j):
    global visited, paper
    
    if paper[i][j] == 1: #직사각형 내부일 경우(1일 경우) 함수를 넘김
        visited.append([i, j])
        return 
    
    block = [] #함수 안에서만 쓰일 블록
    queue = [[i, j]] #함수 안에서만 쓰일 큐
    
    while queue:
        [i, j] = queue.pop(0)
        block.append([i, j]) #블록에 쌓아줌
        visited.append([i, j]) #방문 리스트에 쌓아줌
        
        if paper[i][j] == 0: #각각 상하좌우를 확인하는 조건문
            if i < M-1 and paper[i+1][j] == 0 and [i+1, j] not in block and [i+1, j] not in queue:
                queue.append([i+1, j])
            if j < N-1 and paper[i][j+1] == 0 and [i, j+1] not in block and [i, j+1] not in queue:
                queue.append([i, j+1])
            if i > 0 and paper[i-1][j] == 0 and [i-1, j] not in block and [i-1, j] not in queue:
                queue.append([i-1, j])
            if j > 0 and paper[i][j-1] == 0 and [i, j-1] not in block and [i, j-1] not in queue:
                queue.append([i, j-1])

    return len(block) #블록의 크기만 출력하면 된다


#입력
M, N, K = map(int, input().split())
paper = [[0 for _ in range(N)] for _ in range(M)]

#입력 - 직사각형 좌표 내부를 1로 바꾸어줌
for _ in range(K):
    x1, y1, x2, y2 = map(int, input().split())
    for i in range(y1, y2):
        for j in range(x1, x2):
            paper[i][j] = 1


#함수 실행
visited = []
block_list = []

#0,0 부터 M,N까지 각각의 블록에 관하여 함수 실행문
for i in range(M):
    for j in range(N):
        if [i, j] not in visited:
            block = bfs(i, j)
            if block:
                block_list.append(block)


#출력문
print(len(block_list))
for i in sorted(block_list):
    print(i, end= ' ')