[python]伯準/番号のみ/2667番/グラフ
質問する
番号付き問題リンクのみ
図1に示すように、正方形の地図があります.1は家がある場所、0は家がない場所を表します.哲洙はこの地図で団地を定義しようとしたが、それはつながった家の集合であり、団地番号を与えた.ここでつながっているのは、ある家に左右や上下の異なる家があることを意味します.対角線に家がある場合はつながっていません.<【図2】<図1>を単一番号で示す図である.地図を入力してセル数を出力し、各セルの家屋数を昇順に並べてプログラムを作成してください.
入力
1行目は地図サイズN(正方形、横方向と縦方向のサイズが同じ、5≦N≦25)を入力し、次の行は各N個の資料(0または1)を入力する.
最初のローの合計出力数.その後、各園区内の家屋の数を昇順に並べ、各行に1つ出力します.
二重複文で各要素を探索する
要素が1の場合は0に変更し、単数を1に初期化してsearch関数を実行します.
search関数は,現在位置に基づいて上下左右をブラウズし,1時に0となり,その位置を再帰的にsearch関数を実行する.
search関数実行時、セル数をカウントして記録する
search関数が終わると,初めて出会った1と上下左右に接続されたすべての1が0になり,個数を答えに追加するだけで二重複文を探索し続ける.
コード#コード#
番号付き問題リンクのみ
図1に示すように、正方形の地図があります.1は家がある場所、0は家がない場所を表します.哲洙はこの地図で団地を定義しようとしたが、それはつながった家の集合であり、団地番号を与えた.ここでつながっているのは、ある家に左右や上下の異なる家があることを意味します.対角線に家がある場合はつながっていません.<【図2】<図1>を単一番号で示す図である.地図を入力してセル数を出力し、各セルの家屋数を昇順に並べてプログラムを作成してください.
入力
1行目は地図サイズN(正方形、横方向と縦方向のサイズが同じ、5≦N≦25)を入力し、次の行は各N個の資料(0または1)を入力する.
7
0110100
0110101
1110101
0000111
0100000
0111110
0111000
しゅつりょく最初のローの合計出力数.その後、各園区内の家屋の数を昇順に並べ、各行に1つ出力します.
3
7
8
9
方法二重複文で各要素を探索する
要素が1の場合は0に変更し、単数を1に初期化してsearch関数を実行します.
search関数は,現在位置に基づいて上下左右をブラウズし,1時に0となり,その位置を再帰的にsearch関数を実行する.
search関数実行時、セル数をカウントして記録する
search関数が終わると,初めて出会った1と上下左右に接続されたすべての1が0になり,個数を答えに追加するだけで二重複文を探索し続ける.
# url : https://www.acmicpc.net/problem/2667
# 난이도 : silver 1
import sys
def search(i,j):
global house
if i < n-1 and map[i+1][j] == 1:
house += 1
map[i+1][j] = 0
search(i+1,j)
if j < n-1 and map[i][j+1] == 1:
house += 1
map[i][j+1] = 0
search(i,j+1)
if i > 0 and map[i-1][j] == 1:
house += 1
map[i-1][j] = 0
search(i-1,j)
if j > 0 and map[i][j-1] == 1:
house += 1
map[i][j-1] = 0
search(i,j-1)
n = int(input())
map = [[ int(i) for i in sys.stdin.readline().rstrip()] for _ in range(n)]
answer = []
for i in range(n):
for j in range(n):
if map[i][j] == 1:
map[i][j] = 0
house = 1
search(i,j)
answer.append(house)
print(len(answer))
for i in sorted(answer):
print(i)
Reference
この問題について([python]伯準/番号のみ/2667番/グラフ), 我々は、より多くの情報をここで見つけました https://velog.io/@gandi0330/Python-백준-단지번호붙이기-2667번-그래프テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol