[백준/bfs] 2583: 영역 구하기

-문제:https://www.acmicpc.net/problem/2583

2776번, 단지 붙이기와 같은 유형의 문제다

bfs문제로 풀기 어렵지 않은 문제다

스스로 푼 문제. silver level1이다 

문제에서 갯수와 각각의 빈공간의 갯수 출력하는 건데 잘 안보고 풀었더니 초반에 몇번 틀렸다.

문제 자세히 보는 건 기본!!

 

-주의 해야할 부분: 

 

1. bfs를 보면 ans=0에서 시작하기 때문에 처음 시작하는 한 칸의 갯수를 덜 센다

그래서 각각의 결과에 1을 더해줘야한다. 이거 때문에 마지막에 꽤 시간을 소요했다

 

 

2. 주어진 순서대로 행,열이라고 생각했는데 주어진 위치와 테이블 인덱스는 반대이므로 a,b,c,d로 받고

(b,a),(d,c) 순서로 생각하고 직사각형을 채워야한다 

 

 

-정답풀이: 

from collections import deque
m,n,k=map(int,input().split())
graph=[[0]*n for _ in range(m)]
dx=[-1,1,0,0]
dy=[0,0,-1,1]
#사각형 있는 곳 채우기(b,a)~(d,c)
for _ in range(k):
    a,b,c,d=map(int,input().split())
    for i in range(b,d):
        for j in range(a,c):
            graph[i][j]=1
            
def bfs(x,y):
    global ans
    queue=deque()
    queue.append([x,y])
    graph[x][y]=1
    while queue:
        x,y=queue.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if 0<=nx<m and 0<=ny<n:
                if graph[nx][ny]==0:
                    graph[nx][ny]=1
                    queue.append([nx,ny])
                    ans+=1
ans=0
cnt=0
result=[]
for i in range(m):
    for j in range(n):
        if graph[i][j]==0:
            bfs(i,j)
            cnt+=1
            result.append(ans)
            ans=0
print(cnt)
result.sort()
for i in range(cnt):
    print(result[i]+1,end=' ')

-틀린풀이: