[백준] [Python] 2583번 영역 구하기 - BFS

www.acmicpc.net/problem/2583

2583번: 영역 구하기

 

 

Python

import sys
from collections import deque

m,n,k = map(int,sys.stdin.readline().split())
paper = [[0 for _ in range(m)] for _ in range(n)]
visit = [[0 for _ in range(m)] for _ in range(n)]
for _ in range(k):
    x1,y1,x2,y2 = map(int, sys.stdin.readline().split())
    for i in range(x1,x2):
        for j in range(y1,y2):
            paper[i][j] = 1
#print(paper)


dx=[0,0,1,-1]
dy=[1,-1,0,0]

area = []
q = deque()
for i in range(n):
    #print(i)
    for j in range(m):
        #print( i,j,paper[i][j],visit[i][j])
        if paper[i][j] == 0 and visit[i][j] ==0:
            q.append((i,j))
            
            #print(q)
            temp = 1
            while q:
                y, x = q.popleft()
                
                for t in range(4):
                    nx, ny = x+dx[t], y+dy[t]
                    if 0<=nx<m and 0<=ny<n:
                        if visit[ny][nx] == 0 and paper[ny][nx]==0:
                            temp+=1
                            visit[ny][nx] = visit[y][x]+1
                            q.append((ny,nx))
                            
            if temp != 1: temp-=1
            area.append(temp)

            #for i in range(n):
            #    print(visit[i],paper[i])
            
area.sort()
print(len(area))
for x in area:
    print(x, end=" ")

 

 

 

짧은 풀이

• 각 구역 당 면적을 일일이 출력해야 할 때는 각 점에 대한 for문 안에서 bfs while문을 돌리는 것이 편하다.
  • 그러면 해당 시작점에서 칠해지는 면적을 +1함으로써 확실하게 체크할 수 있다. (temp변수)