Graph Traversal count clouds [python]

Question

Given a 2D grid skyMap composed of '1's (clouds) and '0's (clear sky), count the number of clouds.

A cloud is surrounded by clear sky, and is formed by connecting adjacent clouds horizontally or vertically. You can assume that all four edges of the skyMap are surrounded by clear sky.

Example

skyMap = [['0', '1', '1', '0', '1'],
          ['0', '1', '1', '1', '1'],
          ['0', '0', '0', '0', '1'],
          ['1', '0', '0', '1', '1']]

the output should be

countClouds(skyMap) = 2;

For

skyMap = [['0', '1', '0', '0', '1'],
          ['1', '1', '0', '0', '0'],
          ['0', '0', '1', '0', '1'],
          ['0', '0', '1', '1', '0'],
          ['1', '0', '1', '1', '0']]

the output should be

countClouds(skyMap) = 5.

Answer 1

This can be solved by computing connected components directly on the sky map matrix. We can use the data structure of Disjoint-set.

In this example, the implementation of Disjoint-set (UnionFind) is taken from here:

refs = [[0, 0], [-1, 0], [0, -1], [1, 0], [0, 1]]
for i in range(len(skyMap)):
    for j in range(len(skyMap[i])):
        print i, j
        for dy, dx in refs:
            is_neighbour_valid = 0 <= (i + dy) < len(skyMap) and 0 <= (j + dx) < len(skyMap[i])
            if not is_neighbour_valid:
                continue

            current_cell, neighbour_cell = skyMap[i][j] == '1', skyMap[i + dy][j + dx] == '1'
            if current_cell and is_neighbour_valid:
                ds.union((i, j), (i + dy, j + dx))

# The number of connected components:
print len(set(ds.parents.values()))

For every entry with value '1' we create a set. If it is adjacent to another such entry, we unite the two sets. At the end, we get a set of disjoint sets, and each one represents a cloud. In this code, ds.parents gives us access to the clouds' "representatives", so we can tell the number of clouds.