백준 2583 (실버1): 영역 구하기 (bfs, Python)

문제

2583번: 영역 구하기

 

이미지 출처 : 백준사이트

 

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를 돌려서 풀었다.

백준의 단지번호 붙이기와 매우 유사한 문제였다.

 

 

사실 오늘 냅색 알고리즘을 복습했는데 머리 빠개지는줄 알았다..

흑흑스 갈길이 넘멀다

파이팅..

 

 

 

 

백준 2667: 단지번호붙이기 (Python, C++) - dfs