BOJ 2583 _ 영역 구하기 _ 파이썬

📃 문제

백준 2583번 영역 구하기

알고리즘 - BFS

주의할 점 :

• 입력 순서는 M, N, K이고 M이 행의 수 ,N이 열의 수 이다.
• 꼭짓점 좌표를 (x,y)로 입력받지만 이 문제의 규칙으로 생각하면 (0,0)이 맨 왼쪽 아래이기 때문에 우리가 아는 좌표로 생각하면 (y,x)인셈이다. --> 그렇다면 상하 반전을 해야한다 !
• 출력하는 각 넓이는 오름차순. 그러므로 좌표상의 영역 위치대로 저장해 둘 필요 없다.

💡 풀이 과정

1) BFS 🥳

• 상하 반전

for _ in range(k):
    a,b,c,d = map(int,input().split())
    # 좌표를 밑으로 뒤집는다고 생각하면
    # (a,b) 는 (b,a)인 셈임
    # (b,a)  (b,c)
    # (d,a)  (d,c)
    for i in range(b,d):
        for j in range(a, c):
            arr[i][j] = -1

전체 코드

import sys
input = sys.stdin.readline
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):
    a,b,c,d = map(int,input().split())
    for i in range(b,d):
        for j in range(a, c):
            arr[i][j] = -1 #상하반전으로 저장. 직사각형 둔 곳이 -1

di = [0,1,0,-1]
dj = [1,0,-1,0]

areacnt = []
cnt = 1
for i in range(m):
    for j in range(n):
        if arr[i][j] == 0:
            queue = deque([(i,j)])
            arr[i][j] = cnt
            cnt+=1
            while queue:
                qi, qj = queue.popleft()
                for d in range(4):
                    nexti , nextj = qi+di[d] , qj+dj[d]
                    if 0<=nexti<m and 0<=nextj<n:
                        if arr[nexti][nextj] == 0:
                            queue.append((nexti, nextj))
                            arr[nexti][nextj] = cnt
                            cnt+=1
            areacnt.append(cnt-1)
            cnt = 1
print(len(areacnt))
print(' '.join(map(str,sorted(areacnt))))

2) DFS

🔍 정리 & 배운 것

숫자 배열 초기화

N X M 의 2차원 행렬이라면

arr = [[0 for _ in range(M)] for _ in range(N)]