문제
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 |