[백준] 2583 영역구하기 bfs 실1

이제 bfs 문제 보면 대충 그림+빙산 조합으로 풀면 되겠네...이런 생각 함

 

from collections import deque

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

for _ in range(k):
    x1, y1, x2, y2 = map(int, input().split())
    for y in range(y1, y2):
        for x in range(x1, x2):
            arr[m - y - 1][x] = 1  

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

def bfs(y, x, visited):
    q = deque()
    q.append((y, x))
    visited[y][x] = 1
    cnt = 1
    while q:
        cur_y, cur_x = q.popleft()
        for i in range(4):
            x_ = cur_x + dx[i]
            y_ = cur_y + dy[i]
            if 0 <= x_ < n and 0 <= y_ < m and visited[y_][x_] == 0 and arr[y_][x_] == 0:
                visited[y_][x_] = 1
                q.append((y_, x_))
                cnt += 1
    return cnt

visited = [[0 for _ in range(n)] for _ in range(m)]
cnt = 0
areas = []

for i in range(m):
    for j in range(n):
        if visited[i][j] == 0 and arr[i][j] == 0:
            area_size = bfs(i, j, visited)
            areas.append(area_size)
            cnt += 1


print(cnt) 
print(" ".join(map(str, sorted(areas))))

 

그림 문제 풀이랑 비슷한듯

 

근데 입력받을 때, 좌표가 좌측 하단에서 시작되는 걸 기준으로 하기 때문에

y축을 반전시켜서 입력받아야 직관적으로 풀 수 있다는 점을 조심해야될 것 같다 (m-y-1) ㅇㅇ.

 

그 점 제외하고는 떠올리는 것이 어렵진 않다

 

방문한 적이 없고, 직사각형 영역이 없는 공간이면 bfs를 돌려서 너비를 구한다

bfs 함수는 해당 영역의 너비를 return한다

 

각 너비를 배열에 누적 저장하고,

최종적으로 배열 요소를 sort해서 크기 순으로 공백을 두고 출력한다

 

이제 실버 난이도는 걍 푸는데 골드 좀 쉽게 풀고 싶다