Coding Tests

Ice trays and connected components

#BOJ 2667 · Original problem ↗ Flood fill · BFS / DFS · Connected components

Pour water into an ice tray and it fills the empty cells connected up, down, left and right. Each group is a connected component. BOJ 2667, commonly translated as “Numbering Housing Complexes,” applies this idea to houses: count the groups and report their sizes.

The maps below were created for this guide. Predict the number of groups before playing. Switching to “Housing · group ones” changes the target from 0 to 1.

INTERACTIVE LABIce trays and connected components

Current state

How the solution works

  1. Scan every cell. An undiscovered target cell starts a new component.
  2. Mark a cell when adding it to the DFS stack or BFS queue. This prevents different neighbors from adding it repeatedly.
  3. Visit all reachable four-way neighbors and count the cells. When the frontier is empty, resume the scan.
  4. Sort the collected component sizes.

The first example produces 4 components with sizes [2, 4, 4, 4]. One traversal reaches every cell connected to its seed and cannot cross a wall. It therefore finds exactly one component. BFS and DFS differ in visitation order, not in the groups they find.

Complexity and pitfalls

For an N × N grid with K components, traversal takes O(N²) and sorting takes O(K log K). Total time is O(N² + K log K); extra space is O(N²). The iterative DFS below does not depend on Python’s recursion limit.

Diagonal contact does not connect houses. The diagonal preset has 13 components. Remember that the ice tray fills zeros while the BOJ solution groups ones. The experiment stores frames for playback; the solution code does not need this additional history.

Solution code written for this guide

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')

References and further experiments