質問する

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

入力

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

しゅつりょく

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

マイコード

# 문제 주소 : https://www.acmicpc.net/problem/2667

import sys

N = int(sys.stdin.readline())
MAP = [ sys.stdin.readline().rstrip() for i in range(N) ]
visited_apt = []
result = []

for i in range(len(MAP)):
    for j in range(len(MAP)):
        if (i, j) not in visited_apt:
            if MAP[i][j] == "1":
                stack = set([(i, j)])
                cnt = 0
                while stack:
                    apt = stack.pop()
                    cnt += 1
                    if apt not in visited_apt:
                        visited_apt.append(apt)
                        if apt[0] > 0 and MAP[apt[0]-1][apt[1]] == "1" and (apt[0]-1, apt[1]) not in visited_apt:
                            stack.add((apt[0]-1, apt[1]))
                        if apt[0] < N-1 and MAP[apt[0]+1][apt[1]] == "1" and (apt[0]+1, apt[1]) not in visited_apt:
                            stack.add((apt[0]+1, apt[1]))
                        if apt[1] > 0 and MAP[apt[0]][apt[1]-1] == "1" and (apt[0], apt[1]-1) not in visited_apt:
                            stack.add((apt[0], apt[1]-1))
                        if apt[1] < N-1 and MAP[apt[0]][apt[1]+1] == "1" and (apt[0], apt[1]+1) not in visited_apt:
                            stack.add((apt[0], apt[1]+1))

                result.append(cnt)
        else:
            visited_apt.append((i, j))

print( len(result) )
print( "\n".join(map(str, sorted(result))) )

1時間ぐらいかかってやっと解けた.DFSを用いて解凍しながらset()を用いて同じ場所をさらに探索し,重複を解消した.これはどれくらい時間がかかったのか...