The problem you are trying to solve is called counting the connectedcomponents of a graph.
However, which graph are we talking about? Is it:
 the grid, where each cell of the square matrix is a node in the graph, adjacent to the adjacent cells;
 the graph whose adjacency matrix is this square matrix?
Consider for instance the following matrix:
[[1,1,0,1],
[1,1,0,0],
[0,0,1,0],
[1,0,0,1]]
Your algorithm counts 5 groups in this matrix. This is expected because there are visually five groups in the grid:
[[A,A,0,B],
[A,A,0,0],
[0,0,C,0],
[D,0,0,E]]
However, this matrix is the adjacency matrix of the following graph:
0  1

3 2
Which, as you can see, only has two groups {0, 1, 3} and {2}.
How to fix it
As far as I can see, your algorithm works perfectly to count the number of connected components in the grid. But that is not what you are interested in. You are interested in the number of connected components in the graph represented by this adjacency matrix. You can keep your functions groupcheck
and countGroup
, whose logic is good, but you should modify them so that a node of the graph is given by just one index i
rather than by a pair of indices (i,j)
; and so that two nodes i
and j
are considered adjacent by groupcheck
if there is a 1 in matrix[i][j]
.
Your function groupcheck
currently “erases” cells which have already be counted by setting their value to 0 with the line matrix[i][j] = 0
.
I suggest replacing this by maintaining a set of unseen nodes.
def groupcheck(i, matrix, unseen):
for j in range(len(matrix)):
if (j in unseen) and matrix[i][j]: # if i and j are adjacent
unseen.discard(j)
groupcheck(j, matrix, unseen)
def countGroup(matrix):
count = 0
unseen = set(range(len(matrix)))
while unseen:
i = unseen.pop()
count += 1
groupcheck(i, matrix, unseen)
return count
Complexity analysis: the complexity of countGroup
is n
times the complexity of groupcheck
. Unfortunately, groupcheck
can make up to n
recursive calls, and each recursive call contains a for
loop, so the complexity of groupcheck
is O(n^2)
.
CLICK HERE to find out more related problems solutions.