#BOJ 2667 · 問題文 ↗
Flood fill · BFS / DFS · Connected components
製氷皿に水を注ぐと、上下左右につながる空きマスがひとまとまりになります。これがグラフの連結成分です。BOJ 2667「단지번호붙이기」は、つながった住宅をまとめ、団地の数と各団地の住宅数を求める問題です。
下のマップはこの解説用に作成した例です。成分の数を予想してから再生してください。「住宅・1をまとめる」に切り替えると、探索対象が0から1になります。
現在の状態
解法の考え方
- 全マスを順に調べます。対象のマスが未発見なら、新しい成分の探索を始めます。
- DFSのスタックやBFSのキューに入れる時点で訪問を記録します。複数の隣接マスから重複して追加されるのを防げます。
- 上下左右につながるマスをすべて処理し、大きさを数えます。探索待ちが空になったら走査を再開します。
- 成分の大きさを昇順に整列します。
最初の例は4成分、大きさ [2, 4, 4, 4]です。1回の探索は始点につながるすべてのマスに到達し、壁を越えることはありません。そのため、ちょうど1つの連結成分を求められます。BFSとDFSで異なるのは訪問順だけです。
計算量と注意点
N × NのマップとK個の成分に対し、探索はO(N²)、整列はO(K log K)です。全体の時間計算量はO(N² + K log K)、追加空間はO(N²)です。下の反復型DFSは再帰の深さ制限に依存しません。
斜めに接するだけでは同じ成分になりません。斜めの例では13成分になります。製氷皿では0、BOJのコードでは1を探索する違いにも注意してください。実験は再生用の履歴を保存しますが、解答コードには不要です。
この解説のために作成したコード
Python 3
import sys
def component_sizes(grid):
n = len(grid)
seen = [[False] * n for _ in range(n)]
sizes = []
for r in range(n):
for c in range(n):
if grid[r][c] != '1' or seen[r][c]:
continue
stack = [(r, c)]
seen[r][c] = True
size = 0
while stack:
y, x = stack.pop()
size += 1
for dy, dx in ((-1, 0), (0, 1), (1, 0), (0, -1)):
ny, nx = y + dy, x + dx
if (0 <= ny < n and 0 <= nx < n
and grid[ny][nx] == '1' and not seen[ny][nx]):
seen[ny][nx] = True
stack.append((ny, nx))
sizes.append(size)
return sorted(sizes)
if __name__ == '__main__':
n = int(sys.stdin.readline())
grid = [sys.stdin.readline().strip() for _ in range(n)]
sizes = component_sizes(grid)
print(len(sizes))
print(*sizes, sep='\n')