[백준 #2583,Python] 영역구하기

[문제]

눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다.

예를 들어 M=5, N=7 인 모눈종이 위에 <그림 1>과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 <그림 2>와 같이 3개의 분리된 영역으로 나누어지게 된다.

<그림 2>와 같이 분리된 세 영역의 넓이는 각각 1, 7, 13이 된다.

M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작성하시오.

 

[풀이]

나는 진짜 개 웃긴놈,,,좌표가 평상시에 쓰는 거랑 다르게 생겼는데 (행열반대에, 행도 반대로 세고, 또 그래프 교축?의 좌표가 주어져서) 그거를 원래대로 바꾸니라 30분씀^~^ 데헷! BFS문제로 처음에 각 빈공간의 영역의 시작점,,? 을 어떻게 찾지라고 엄청 생각하다가 그냥 단순하게 for문 전체다 돌려서 (어차피 빈공간 하나 잡히는 순간 같은 영역애들은 dfs에서 자동으로 visit 처리 되니까 걱정 안해두 되는뎅~) 풀면 해결! 아 기쁘다! 

백트래킹이나 조합은 평생 안하고 그나마 dfs나 bfs하고싶다~!

def change(a,b): #
    r,c = b,a
    r = N - r
    return(r,c)
def bfs(area):
    global cnt
    dr = [-1,1,0,0] #상,하,좌,우
    dc = [0,0,-1,1]

    while queue:
        r,c = queue.pop(0)
        visited[r][c] = 1
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0<=nr<N and 0<=nc<M and arr[nr][nc] == 0 and visited[nr][nc] == 0:
                queue.append((nr,nc))
                visited[nr][nc] = 1
                area += 1
    cnt += 1
    return area

N, M, K = map(int,input().split())
arr = [[0]*M for _ in range(N)] #전체 사각형 만들어주기

for _ in range(K):
    ly,lx,ry,rx=map(int,input().split())
    r1,c1 = change(ly,lx)
    r2,c2 = change(ry,rx)
    for i in range(r2,r1):
        for j in range(c1,c2):
            arr[i][j] = 1
queue = []
result = []
cnt = 0 #영역의 개수
visited = [[0]*M for _ in range(N)]
for r in range(N):
    for c in range(M):
        if arr[r][c] == 0 and visited[r][c] == 0:
            queue.append((r,c))
            result.append(bfs(1))
print(cnt)
result.sort()
print(*result)