[백준] 2583번 영역 구하기

 

아이디어

그림을 돌려서 생각하기

좌표 위치 때문에 어떻게 풀어야 할지 몰랐는데 돌려서 생각하니 쉽게 풀 수 있었다.

문제의 그림을 시계 방향으로 반바퀴 돌려서 생각해보자.

 

(0,0)

		0,2	0,3
	1,1	1,2	1,3	1,4
		2,2	2,3
		3,2	3,3
4,0	4,1
5,0	5,1

                                                  (7,5)

 

편안..

위와 같이 그림을 이렇게 돌려놓고 보는게 문제 풀기에 자연스럽다.

그럼 이제 가로길이가 m, 세로가 n인 직사각형이 되었다.

 

다음 단계로 넘어가 직사각형 영역을 칠해주는 것부터는 오히려 쉽다.

직사각형 왼쪽아래 좌표를 (x,y) 오른쪽위 좌표를 (x2,y2) 로 입력받는다.

0 2 4 4 로 입력 받았다면 색칠할 영역은 (0,2)~(3,3) 까지이다.

색칠할 영역을 반복문으로 돌며 1로 채워준다.

 

해결

area 배열에는 분리된 영역의 넓이(정수)를 저장한다.

마지막에 한줄로 출력시 int를 str으로 변환후 join 하는 것에 주의!

(area를 그냥 넣으면 정수배열이기 때문에 오류난다)

def bfs(x,y):
    q=deque()
    q.append((x,y))
    graph[x][y]=1       #시작노드 큐에 넣고 방문처리
    dx=[-1,1,0,0]
    dy=[0,0,-1,1]
    cnt=1
    while q:
        x,y=q.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if nx<0 or ny<0 or nx>=n or ny>=m:
                continue
            if graph[nx][ny]==1:
                continue
            if graph[nx][ny]==0:
                cnt+=1
                q.append((nx,ny))
                graph[nx][ny]=1     #큐에 넣고 방문처리
    return cnt
    
from collections import deque
import sys
input = sys.stdin.readline

m,n,k=map(int,input().split())
graph=[[0 for _ in range(m)] for __ in range(n)]
area=[]

for i in range(k):
    x,y,x2,y2 = map(int,input().split())
    for j in range(x,x2):
        for l in range(y,y2):
            graph[j][l]=1
    
for i in range(n):
    for j in range(m):
        if graph[i][j]==0:
            area.append(bfs(i,j))
print(len(area))
area.sort()
print(' '.join(list(map(str,area))))