[アルゴリズム]BOJ 2667園区番号を貼る
10159 ワード
[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)Reference
この問題について([アルゴリズム]BOJ 2667園区番号を貼る), 我々は、より多くの情報をここで見つけました https://velog.io/@isayaksh/알고리즘-BOJ-2667-단지번호붙이기テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol