backjun-領域を求める(2583)

Graph Search(BFS)

質問する

ルーラーピッチ1のM×N(M,N≦100)サイズの四角紙があります.この四角紙にK個の矩形を目盛りで描画すると、これらK個の矩形の内部を除いて、残りの部分はいくつかの別々の領域に分割される.
例えば、M=5、N=7の四角紙に<図1>のように3つの矩形を描くと、残りの領域は<図2>のように3つの独立した領域に分割される.

「図2」に示すように、3つの領域の幅はそれぞれ1、7、13である.
M,N,K,K個の矩形の座標が与えられると,K個の矩形の内部を除いた残りの部分をいくつかの独立した領域に分割し,各分離領域の幅を求めることで出力プログラムを記述する.

入力

第1行MとN,Kは、スペースを隔てて順次与えられる.M,N,Kはいずれも100以下の自然数である.2行目からK行目まで、矩形左下角頂点のx、y座標値、右上角頂点のx、y座標値は、行ごとにスペースを隔てて順次与えられる.四角い紙の左下の頂点の座標は(0,0)、右上の頂点の座標は(N,M)です.入力したK個の長方形は、丸み紙全体を埋めません.

しゅつりょく

最初の行の区切り領域の数を出力します.2行目は各領域の幅を昇順に並べ、スペースを隔てて印刷します.

from collections import deque

def bfs(x, y):
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    count = 1 # 현재의 해당 노드를 방문 => 카운트 하나 올리고 시작
    
    queue = deque()
    queue.append((x, y))
    
    graph[x][y] = 1 # 해당 노드 방문을 1로 표시
    
    while queue:
        now = queue.popleft()
        
        for i in range(4):
            nx = now[0] + dx[i]
            ny = now[1] + dy[i]
            
            if (0 <= nx < M) and (0 <= ny < N): # 가까운 노드부터 탐색 시작 부분
                if graph[nx][ny] == 0:
                    graph[nx][ny] = 1 # 방문했을 때근처 노드 0 이면 1로 표시
                    queue.append((nx, ny)) # queue에 넣고 또 주변 노드 탐색 시작
                    count += 1 # 넓이 1추가
    return count

M, N, K = map(int, input().split())
graph = [[0] * N for _ in range(M)]
result = []
total = 0

for _ in range(K):
    x1, y1, x2, y2 = map(int, input().split())
    
    for i in range(y1, y2):
        for j in range(x1, x2):
            graph[i][j] = 1
            
for i in range(M):
    for j in range(N):
        if graph[i][j] == 0:
            total += 1
            result.append(bfs(i, j))
            
result.sort()
print(total)
print(*result)

BFS=>deque(アクセスするかどうか)+ノードの上下左右のノードにナビゲート
ナビゲーションノードの上下左右に使用するdx,dy=>デバイス
参照)
https://fullmoon1344.tistory.com/86
https://juhee-maeng.tistory.com/133