[アルゴリズム]BOJ 2667園区番号を貼る

[BOJ]2667园区号码短片

📍 質問する

図1に示すように、正方形の地図があります.1は家がある場所、0は家がない場所を表します.哲洙はこの地図で団地を定義しようとしたが、それはつながった家の集合であり、団地番号を与えた.ここでつながっているのは、ある家に左右や上下の異なる家があることを意味します.対角線に家がある場合はつながっていません.<【図2】<図1>を単一番号で示す図である.地図を入力してセル数を出力し、各セルの家屋数を昇順に並べてプログラムを作成してください.

📍 入力

1行目は地図サイズN(正方形、横方向と縦方向のサイズが同じ、5≦N≦25)を入力し、次の行は各N個の資料(0または1)を入力する.

📍 しゅつりょく

最初のローの合計出力数.その後、各園区内の家屋の数を昇順に並べ、各行に1つ出力します.

📍 に答える

ハーモニー

from collections import deque
from sys import stdin

def BFS(x, y):
  D = deque([[x, y]])
  count = 0
  while D:
    [x, y] = D.popleft()
    if x - 1 >= 0 and MAP[y][x-1]: # MAP 범위 내에 아파트가 존재한다면
      D.append([x-1, y]) # 다음 아파트 추가
      MAP[y][x-1] = 0 # 다음 아파트 MAP에서 제거
      count += 1 # 아파트 갯수 추가
    if x + 1 < N and MAP[y][x+1]:
      D.append([x+1, y])
      MAP[y][x+1] = 0
      count += 1
    if y - 1 >= 0 and MAP[y-1][x]:
      D.append([x, y-1])
      MAP[y-1][x] = 0
      count += 1
    if y + 1 < N and MAP[y+1][x]:
      D.append([x, y+1])
      MAP[y+1][x] = 0
      count += 1
  return count # 형성된 단지내 아파트 갯수

N = int(stdin.readline())
MAP = []
answer = []
for _ in range(N):
  MAP.append(list(map(int,stdin.readline().rstrip())))

for x in range(N):
  for y in range(N):
    if MAP[y][x]:
      answer.append(BFS(x,y))
answer.sort()
print(len(answer))
for a in answer:
  print(a)