티스토리 뷰
728x90
반응형
문제
모눈종이 위에 k개의 직사각형을 그릴 때, 직사각형이 그려지지 않은 부분이 몇 개의 분리된 영역으로 나누어진다.
예를 들어 m = 5, n = 7 인 모눈종이 위에 3개의 직사각형을 그렸을 때, 다음과 같이 3개의 영역으로 나누어질 수 있다.
각각의 넓이는 1, 7, 13이다.
이와 같이 직사각형에 포함되지 않는 분리된 영역의 각 크기를 오름차순으로 출력하는 문제이다.
풀이
- 먼저 주어진 직사각형을 모눈종이 영역에 표시한다.
- 이때 본 문제에서는 상하좌우 방향을 유의해야 한다.
- 여기서는 직사각형이 차지하는 공간이 중요한 부분임으로
임의로 row를 m, col를 n으로 보고,
왼쪽 아래 꼭짓점의 x1, y1좌표값과 오른쪽 위 꼭짓점의 x2, y2좌표값을 왼쪽 위, 오른쪽 아래로 가정하였다.
(편의상 상하반전한 상태로 가정함)
- 모눈종이를 순회하면서 직사각형에 포함되지 않는 영역의 크기를 dfs를 통해 구한다. (bfs도 가능)
- 별도 리스트에 담아 개수와 영역의 크기를 정렬하고 출력한다.
알고리즘
- 영역의 크기를 구하기 위한 DFS를 정의한다.
- 스택에 시작점을 담는다.
- 시작점을 카운트(cnt)하고, 1로 값을 입력하여 방문을 체크한다.
- 스택에서 좌표를 꺼내면서 상하좌우를 탐색한다.
- 이때 모눈종이 바깥과 직사각형 혹은 방문한 영역을 제외하고 탐색한다.
- 이동 가능한 위치라면 스택에 담으며 방문을 체크(1)하고, 영역 크기(cnt)를 더해준다.
- 스택에 더 이상 남은 좌표가 없다면 영역 크기를 return 한다.
- 모눈종이 영역을 0으로 초기화한다.
- 주어진 직사각형 좌표를 통해 직사각형을 표시한다.
- for문을 돌면서 1을 입력한다.
- (0,0)부터 (m, n)까지 순회하면서 비어있는 곳이라면 앞서 정의한 DFS를 통해 비어있는 영역의 크기를 구한다.
- 구한 값을 areas 리스트에 담는다.
- 영역의 개수를 출력한다.
- sort를 통해 오름차순으로 정렬한 영역의 크기들을 출력한다.
Python 코드
import sys
input = sys.stdin.readline
# 모눈종이 안의 범위인지 체크
def in_range(x,y):
return 0<=x<m and 0<=y<n
# dfs 를 사용해 영역의 크기를 세준다.
def dfs(i, j):
stack = [(i, j)]
dx, dy = (0, 0, 1, -1), (1, -1, 0, 0)
cnt = 1
arr[i][j] = 1
while stack:
x, y = stack.pop()
for d in range(4):
nx, ny = x + dx[d], y + dy[d]
if not in_range(nx,ny): # 모눈종이 바깥 제외
continue
if arr[nx][ny]: # 직사각형 및 방문 영역 제외
continue
cnt += 1
stack.append((nx, ny))
arr[nx][ny] = 1
return cnt
m, n, k = map(int, input().split())
# 빈공간이면 0 직사각형이 있으면 1
arr = [[0] * n for _ in range(m)]
# 직사각형에 해당하는 범위 색칠
for _ in range(k):
y1, x1, y2, x2 = map(int, input().split())
for i in range(x1, x2):
for j in range(y1, y2):
arr[i][j] = 1
# dfs를 통해 분리된 영역 넓이 구하기
areas = []
for i in range(m):
for j in range(n):
if not arr[i][j]:
areas.append(dfs(i, j))
print(len(areas)) # 영역 개수
areas.sort() # 오름차순 정렬
print(*areas) # 영역 크기
문제출처
2583번: 영역 구하기
첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오
www.acmicpc.net
728x90
반응형
'Study > Coding Test' 카테고리의 다른 글
[백준 BOJ / Python] 24524번 아름다운 문자열 (0) | 2023.03.04 |
---|---|
[백준 BOJ / Python] 1080번 행렬 (0) | 2023.03.02 |
[백준 BOJ / Python] 14503번 로봇 청소기 (0) | 2023.02.27 |
[백준 BOJ / Python] 1322번 x와 k (0) | 2023.02.26 |
[백준 BOJ / Python] 14002번 가장 긴 증가하는 부분 수열 4 DP (0) | 2023.02.23 |
댓글