[백준 2583] 영역 구하기

 

2583번: 영역 구하기

 

알고리즘 : DFS

난이도 : 실버Ⅰ

 

1. 문제요약

• 특정 크기의 모눈종이가 주어지고, 직사각형의 왼쪽하단과 오른쪽 상단의 좌표가 주어진다.
• 모눈종이가 직사각형으로 인해 구역이 나누어지게 되는데, 구역의 개수와 각 구역별 넓이를 오름차순으로 출력한다.

2. 구현과정

• DFS의 전형적인 문제이다.
• 처음 맵초기화할 때 모눈종이에서 빈 곳을 True로, 직사각형 부분을 False로 초기화해주었다.
• dfs 함수를 정의하여 사용한다. 기본적으로 area = 1을 return하도록 정의하였는데, 인접 부분이 빈 곳이어서 이동가능한 경우에는 dfs 수행으로 이동된 부분에서 dfs를 수행하여 그 return값을 area에 더해주도록 하였다. 이로써 구역의 넓이를 리턴하게 된다.
• answerlist에 구역의 넓이를 저장하고, 구역의 개수는 len(answerlist)를, 구역의 넓이는 answerlist를 오름차순정렬 후 unpacking 해주었다.

3. 파이썬 코드

import sys
sys.setrecursionlimit(10**6)

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

# 모눈종이 초기화 : 직사각형 영역은 False, 빈 곳은 True로
field = [[True]*n for _ in range(m)]
for _ in range(k):
    x1,y1,x2,y2 = map(int,input().split())
    for x in range(x1,x2):
        for y in range(y1,y2):
            field[y][x] = False

# dfs 이동방향
dx = [1,-1,0,0]
dy = [0,0,1,-1]

# dfs 함수
def dfs(x,y):
    field[x][y] = False
    area = 1
    for i in range(4):
        newx, newy = x+dx[i], y+dy[i]
        if 0 <= newx < m and 0 <= newy < n and field[newx][newy]:
            area += dfs(newx,newy)
    return area

# 정답 출력
answerlist = []
for i in range(m):
    for j in range(n):
        if field[i][j]:
            answerlist.append(dfs(i,j))
answerlist.sort()
print(len(answerlist))
print(*answerlist)