백준 2583번: 영역 구하기 - 파이썬(DFS)

dfs방법으로 풀어보았다.

 

이번 문제에서는 print(*list)에 대해서 알 수 있게 되었다.

 

원래는 for 루프를 이용해서 sep연산자와 함께 사용해서 리스트를 출력했었는데

블로그를 통해서 리스트를 파이썬 *연산자와 함께 출력하면 깔끔하게 보기좋게 출력된다.

더 알아보고 싶으신 분들은 

https://www.askpython.com/python/list/print-a-python-list

https://www.daleseo.com/python-lists-print/

위의 링크들 참조하면 좋을것 같다.

import sys
sys.setrecursionlimit(10000)

m,n,k = map(int,input().split())
# 1. 그림그리기
graph = [[0]*n for i in range(m)]

rectangle = []
for i in range(k):
    rectangle.append(list(map(int,input().split())))

# 2. 그린 그림에 표시하기
for point in rectangle:
    for x in range(point[0],point[2]):
        for y in range(point[1],point[3]):
            graph[y][x] = 1

# 3. 상하좌우 
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]

# dfs - 분리된 영역의 크기 구하는 함수
def dfs(x,y,cnt):
    graph[x][y] = 1
    for dx,dy in d:
        X,Y = x+dx, y+dy
        if 0 <= X < m and 0 <= Y < n and graph[X][Y] == 0:
            cnt = dfs(X,Y,cnt+1)
    return cnt

# 분리된 영역 구하기
res = []
for i in range(m):
    for j in range(n):
        if graph[i][j] == 0:
            res.append(dfs(i,j,1))

print(len(res))
print(*sorted(res))