0

I'm confused. I don't understand how visited can be updated in numIslands by making a change in DFS.

The way I understood it was that visited, once passed into DFS, is like a copy of the original visited.

Is this not the case?

class Solution:
    def DFS(self, grid, visited, i, j):
        if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or visited[i][j] or grid[i][j] == '0':
            return
        visited[i][j] = True
        self.DFS(grid, visited, i+1, j)
        self.DFS(grid, visited, i-1, j)
        self.DFS(grid, visited, i, j+1)
        self.DFS(grid, visited, i, j-1)
        
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid: return 0
        visited = [[False for i in range(len(grid[0]))] for j in range(len(grid))]
        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1' and visited[i][j] == False:
                    self.DFS(grid, visited, i, j) # TODO
                    count += 1
        return count
Rivers
  • 1,783
  • 1
  • 8
  • 27
lifelonglearner
  • 196
  • 15
  • 3
    Python passes by reference, not by value. The `visited` that appears in `DFS()` is a different name for the same object that you passed from `numIslands()`. You could _reassign_ something to the name `visited` without changing the original value, but if you change _the object to which the name `visited` refers_ (by changing a specific index of it with `visited[i][j] = True`), then the change will persist, because it's the same object. – Green Cloak Guy Oct 30 '20 at 15:04
  • 1
    _"is like a copy of the original visited. Is this not the case?"_ No, you it's not. You can create a copy with https://docs.python.org/3.8/library/copy.html – Thomas Sablik Oct 30 '20 at 15:10
  • Does this answer your question? [List changes unexpectedly after assignment. How do I clone or copy it to prevent this?](https://stackoverflow.com/questions/2612802/list-changes-unexpectedly-after-assignment-how-do-i-clone-or-copy-it-to-prevent) – MisterMiyagi Oct 30 '20 at 16:23

1 Answers1

2

The way I understood it was that visited, once passed into DFS, is like a copy of the original visited.

This is not true. Python never makes implicit copies for you. If you pass an object to a function, a copy of it is not made. You're simply giving the object associated with visited a second name visited within the scope of the function.

To actually have DFS operate independently of visited in numIslands, you'd need to make a deep-copy:

from copy import deepcopy

. . .

self.DFS(grid, deepcopy(visited), i, j)

Although this is often not a great idea since deepcopy is a rather expensive function, and I don't think you'd want to do that here anyways. The algorithm requires that DFS mutate visited. If it didn't, DFS wouldn't do anything since it never returns a value.

Carcigenicate
  • 43,494
  • 9
  • 68
  • 117
  • We could add that: ``` list.copy()``` returns a ```shallow copy``` of the list object, not a ```deep copy```. The difference between deep and shallow : "A shallow copy constructs a new compound object and then (to the extent possible) inserts references into it to the objects found in the original." and "A deep copy constructs a new compound object and then, recursively, inserts copies into it of the objects found in the original". Source: https://docs.python.org/3/library/copy.html – Rivers Oct 31 '20 at 09:22