[백준] 2583 영역 구하기 (실버1) / BFS

문제요약

나의 코드 및 설명

• BFS(너비우선탐색)을 활용하여 문제를 해결하였다. 
• bfs 함수를 통해 직사각형이 없는 좌표(1)를 직사각형이 있는 좌표(0) 값으로 바꿔주고, 이중 for문을 통해 아직 바뀌지 않은 좌표가 있다면 bfs 함수가 실행될 수 있도록 구현하였다.  

from collections import deque

def bfs(sx,sy):
    global num
    queue = deque()
    queue.append((sx,sy))
    visited[sy][sx] = 1
    board[sy][sx] = 0
    num = 1
    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx<0 or ny<0 or nx>=n or ny>=m:
                continue
            else:
                if board[ny][nx] == 1 and visited[ny][nx] == 0:
                    visited[ny][nx] = visited[y][x] + 1
                    board[ny][nx] = 0
                    queue.append((nx,ny))
                    num += 1


m,n,k = map(int, input().split()) #m:세로 n:가로 k:직사각형 개수

board = [[1]*n for _ in range(m)]

#직사각형 그린 부분은 0으로 표시
for _ in range(k):
    x1,y1,x2,y2 = map(int, input().split())
    for i in range(y1,y2):
        for j in range(x1,x2):
            board[i][j] = 0

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

count = 0 #bfs함수 실행 횟수
num = 0
area_list = [] #영역의 크기를 담을 리스트
for i in range(m):
    for j in range(n):
        if board[i][j] == 1:
            visited = [[0]*n for _ in range(m)]
            bfs(j,i) #bfs를 실행하고 오면, 한 번 거쳐간 board 좌표값은 0이 된다.
            area_list.append(num)
            count += 1

area_list.sort()

print(count)
print(" ".join(map(str, area_list)))

피드백

만약 영역의 넓이를 구하는 것이 아니라 최단거리를 구하는 문제였다면, visited 리스트의 값을 이전 좌표 대비 1씩 증가시키는 방식으로 풀이했겠지만, 넓이를 구하는 문제이기 때문에 num값을 1씩 증가시켜서 넓이를 구할 수 있었다.