백준 > 영역 구하기

❓ 문제

백준 실버1 문제 > 영역 구하기

❗ 해결

BFS로 풀었다.

예제 입력에서 5 7 3 이 들어오고 5행 7열짜리 모눈종이와 좌표 3개가 주어진다.
좌표는 (x1, y1) (x2, y2) 형태로 주어진다.
예제에서 (0,2) 부터 (4,4)까지 칠하고, (1,1)부터 (2,5)까지 칠하고 (4,0)부터 (6,2)까지 칠한다.
이것을 코드로 옮겨 보면

m, n, k = map(int, input().split())
board = [[0] * n for _ in range(m)]

for _ in range(k):
    x1, y1, x2, y2 = map(int, input().split())

    for i in range(x1, x2):
        for j in range(y1, y2):
            board[j][i] = 1

먼저 5행 7열짜리 모눈종이는 전부 0으로 초기화하고
좌표를 입력 받아서,해당 좌표 범위 내에 있는 영역은 전부 1로 채워 넣는다 (=칠한다)

count_list = []
area_count = 0

for i in range(len(board)):
    for j in range(len(board[0])):
        if board[i][j] == 0:
            count_list.append(bfs(i, j))
            area_count += 1

그리고 각 영역의 넓이를 담아줄 count_list 와 해당 영역 개수를 담아줄 area_count를 선언한다.

그리고 모눈종이를 반복문으로 돌리면서 칠해지지 않은 곳(=0인 곳)이 있을 경우 bfs를 한다.

def bfs(x, y):
    count = 1
    queue = deque()
    board[x][y] = 1
    queue.append([x, y])

    while queue:

        x, y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < len(board) and 0 <= ny < len(board[0]) and board[nx][ny] != 1:
                board[nx][ny] = 1
                queue.append([nx, ny])
                count += 1

    return count

처음 count는 1로 초기화 해준다(칠하지 않은 곳을 만났으므로)
그리고 해당 방문한 곳은 1로 변경해주고, 1이 아닌 곳을 돌면서 count를 누적시켜준다.
그리고 마지막에 count를 반환한다.

전체코드

from collections import deque

def bfs(x, y):
    count = 1
    queue = deque()
    board[x][y] = 1
    queue.append([x, y])

    while queue:

        x, y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < len(board) and 0 <= ny < len(board[0]) and board[nx][ny] != 1:
                board[nx][ny] = 1
                queue.append([nx, ny])
                count += 1

    return count


m, n, k = map(int, input().split())
board = [[0] * n for _ in range(m)]

count_list = []
area_count = 0

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

for _ in range(k):
    x1, y1, x2, y2 = map(int, input().split())

    for i in range(x1, x2):
        for j in range(y1, y2):
            board[j][i] = 1

for i in range(len(board)):
    for j in range(len(board[0])):
        if board[i][j] == 0:
            count_list.append(bfs(i, j))
            area_count += 1

print(area_count)
print(*sorted(count_list))