백준/ Silver 1 문제 , 백준 파이썬 2583, 영역 구하기 [BFS]

백준/ Silver 1 문제 , 백준 파이썬 2583, 영역 구하기 [BFS]

 

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------
난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>
크게 어려운 거 없는 문제이다. y랑 x 의 위치를 잘생각해서 칸을 채울때 신경써주면 된다.

 

 

<문제 출처>

 

https://www.acmicpc.net/problem/2583

2583번: 영역 구하기

------------------------------------------------------------------------------------------------------------------------------

 

 

좌표라도 입력받은 그대로 for 문 범위를 설정해서 1로 채워준다.

 

그 후 0의 영역들을 카운트 해주었다.

 

 

 

 

 

 

 

------------------------------------------------------------------------------------------------------------------------------

정답

 

 

 

from collections import deque

vertical=[1,-1,0,0]
parallel=[0,0,1,-1]
dq=deque()
result=[]  # 영역의 크기 저장할 공간

N,M,K=map(int,input().split())
paper=[[0 for _ in range(M)]for _ in range(N)]
for i in range(K):
    x1,y1,x2,y2=map(int,input().split())
    for j in range(y1,y2):  # 입력받은 직사각형들 표에 덮어씌우기
        for k in range(x1,x2):
            paper[j][k]=1

def bfs():
    cnt=1
    while dq:
        y,x=dq.popleft()  # y,x 위치 조심!
        for i in range(4):
            my=y+vertical[i]  # 위아래
            mx=x+parallel[i]  # 좌우
            if 0<=my<N and 0<=mx<M:
                if paper[my][mx]==0:
                    dq.append([my,mx])
                    paper[my][mx]=2
                    cnt+=1 
    result.append(cnt)  # 한 영역의 크기 저장
    
for i in range(N):
    for j in range(M):
        if paper[i][j]==0:
            dq.append([i,j])
            paper[i][j]=2
            bfs()
result.sort()  # 정렬
print(len(result))  # 영역이 저장된 수만큼이 영역의 개수
print(*result)