[백준/BOJ] - 2583번 python 풀이 - DFS

---

Key Point

1. 배열의 시작점과 이 문제의 예시 사진의 시작점이 달라도 상관 없기에 (직사각형의 위치가 반전되더라도 결과를 도출하는데 영향 없음) 직사각형에 해당하는 범위를 다른 숫자로 예외처리 해준다.

2. 본인은 전체 배열의 값을 모두 1로 설정해주었고 직사각형에 해당하는 부분을 0으로 변경해주었다.

3. 배열에서 1에 해당하는 부분을 찾았을 경우 그 부분을 기점으로 dfs 알고리즘을 적용시켜 몇개의 영역이 도출되는지 확인한다.

 

알게 된 문법

dx,dy를 set형으로 표시해도 문제를 푸는데 이상 없음

---

import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)
cnt = 0
dx,dy = (-1, 1, 0, 0), (0, 0, -1 ,1)
area = []
val = 0
def dfs(x, y):
    global val
    arr[x][y] = 0
    for i in range(4):
        rx = x+ dx[i]
        ry = y + dy[i]
        if(0<= rx < m) and (0<= ry < n):
            if arr[rx][ry] != 0:
                val +=1
                dfs(rx,ry)

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

for _ in range(k):
    x1, y1, x2, y2 = map(int, input().split()) #(0,2), (4,4)
    for i in range(y1, y2): #(2,4)
        for j in range(x1, x2): #(0,4)
            arr[i][j] = 0 # 0

for i in range(m):
    for j in range(n):
        if arr[i][j] == 1:
            dfs(i,j)
            area.append(val+1)
            val = 0
            cnt+=1
area.sort()

print(cnt)
for item in area:
    print(item, end =' ')