[백준 2583] 영역 구하기

문제

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

2583번: 영역 구하기

알고리즘

1. 주어진 사각형의 좌표를 조회해서 해당영역을 그래프에 1로 채워준다 (초기화 0으로)

2. 2차원 그래프를 조회해서 0으로 시작되는 구역이 나올때 section의 값을 올려준다

3. bfs순회시, 방문때 이미 간 곳은 2로 바꿔준다 

코드

import sys
from collections import deque
 
def input_data():
    readl = sys.stdin.readline
    R, C, K = map(int, readl().split())
    rects = [list(map(int,readl().split())) for _ in range(K)]
    return R, C, K, rects
 
d= ((0,1),(0,-1),(1,0),(-1,0))
def Bfs(i,j):
    visited = [[0]*(C+1) for _ in range(R+1)]
    q = deque()
    q.append((i,j))
    visited[i][j] = 1
    graph[i][j] = 2 #한번 들어온 곳은 2로 변경
    cnt =0
    while q: 
        x, y= q.popleft()
        for dx ,dy in d:
            nx,ny = dx+x, dy+y 
            if not (0<=nx<R and 0<=ny<C): continue
            if visited[nx][ny] == 1 : continue            
            if graph[nx][ny] == 0:   
                cnt +=1
                graph[nx][ny] = 2
                visited[nx][ny] = 1
                q.append((nx,ny))
    return cnt+1

def Solve():
    q= deque()
    for x1,y1, x2,y2 in rects: #사각형의 구역 그리기 
        q.append((x1,y1))
        for i in range (y1,y2):
            for j in range(x1,x2):
                graph[i][j] = 1
    section =0
    width = []
    for i in range(R):
        for j in range(C):
            if graph[i][j] == 0: 
                res = (Bfs(i,j)) #bfs 알고리즘으로 영역 조회
                width.append(res)
                section +=1 #구역의 개수
    width.sort()
    return section, width
                 
 
R, C, K, rects = input_data()
width = []
sol = -1
graph = [[0]*(C+1) for _ in range(R+1)]
visited = [[0]*(C+1) for _ in range(R+1)]
sol,width = Solve()
print(sol)
for i in width:
    print(i, end=" ")

고찰