백준 2583 파이썬 풀이 (영역 구하기, DFS)

이번 문제는 주어진 좌표만큼 색칠된 경우 색칠되지 않은 영역의 넓이와 개수를 구하면 된다.

 

1. 좌표를 배열위치로 바꾸기

2. DFS로 탐색하면서 넓이 구하기

 

이 두가지만 하면된다. 좌표는 그림을 그려서 구해보면 쉽게 확인가능하다.

start = [(m-1-b),(0+a)]

end = [(m-d),(c-1)]

로 바꾸면 된다.

 

그럼 DFS로 탐색하는 코드만 추가해주면 끝이다.

m,n,k = map(int, input().split())

Map = [[0 for i in range(n)] for i in range(m)]

for _ in range(k):
    a,b,c,d = map(int, input().split())
    start = [(m-1-b),(0+a)]
    end = [(m-d),(c-1)]
    for i in range(end[0],start[0]+1):
        for j in range(start[1],end[1]+1):
            Map[i][j] = 1
def DFS(x,y):
    s = [[x,y]]
    Map[x][y] = 1
    dx = [0,0,1,-1] #동서남북
    dy = [1,-1,0,0]
    count = 0
    while s:
        count+=1
        x,y = s.pop()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if (0<=nx<m) and (0<=ny<n) and (Map[nx][ny] == 0):
                s.append([nx,ny])
                Map[nx][ny] = 1
    return count
count=[]
for i in range(m):
    for j in range(n):
        if Map[i][j] == 0:
            count.append(DFS(i,j))
print(len(count))
count.sort()
for i in count:
    print(i, end=' ')

DFS를 계속 풀다보니 조금씩 익숙해지는거 같아서 기분이 아주 좋다~