문제
M,N,K (행, 열, 직사각형 개수)를 입력받고
K개의 직사각형 왼쪽 아래 좌표와 오른쪽 위 좌표를 입력받아 색칠한다.
<그림1> 같이 색칠이 끝나면 <그림2>처럼 직사각형 외부에 분리된 영역들이 생기는데
이 영역들의 넓이를 각각 구하고 영역의 개수를 첫째 줄에 출력,
영역의 넓이를 오름차순으로 각각 출력해주면 되는 문제이다.
풀이 (python, BFS)
from collections import deque
dx=[1,-1,0,0]
dy=[0,0,1,-1]
m,n,k = map(int,input().split())
sq=[[0]*(n) for _ in range(m)] #n*m 맵
#직사각형 좌표 입력 및 색칠
for tc in range(k):
a,b,c,d = map(int,input().split()) #0 2 4 4
for x in range(b,d): #2~4
for y in range(a,c): #0~4
sq[x][y]=1
#BFS
dq=deque()
answer=[]
for i in range(m):
for j in range(n):
if sq[i][j]==0:
dq.append((i,j))
cnt=0
while dq:
cx,cy=dq.popleft()
for i in range(4):
nx=cx+dx[i]
ny=cy+dy[i]
if 0<=nx<m and 0<=ny<n and sq[nx][ny]==0:
cnt+=1
sq[nx][ny]=2 #visit
dq.append((nx,ny))
if cnt==0: answer.append(1)
else: answer.append(cnt)
answer.sort()
print(len(answer))
for a in answer:
print(a,end=' ')
좌표를 입력받고 색칠한 뒤 (1로 표기)
맵에서 0인 영역이 존재하면 해당위치를 큐에 넣고 BFS를 돌려서 풀었다.
백준의 단지번호 붙이기와 매우 유사한 문제였다.
사실 오늘 냅색 알고리즘을 복습했는데 머리 빠개지는줄 알았다..
흑흑스 갈길이 넘멀다
파이팅..
반응형
'Problem Solving > BOJ' 카테고리의 다른 글
백준 1697 : 숨바꼭질 (bfs, Python) (0) | 2022.05.29 |
---|---|
백준 11047 : 동전0 (Greedy, Python) (0) | 2022.05.29 |
백준 1654: 랜선자르기 (Python) - 이진탐색 알고리즘 (0) | 2022.04.22 |
백준 1475: 방 번호 (Python) (0) | 2022.04.09 |
백준 1012: 유기농 배추 (Python) - bfs/ 런타임 에러 (RecursionError), 시간초과 해결 (0) | 2022.03.20 |