문제 설명
행렬에서 섬을 찾기 위해 DFS 구현 문제 (Problem implementing DFS to find islands in a matrix)
섬 수라는 leetcode 문제를 해결하려고 합니다.
'1'(땅)과 '0'(물)의 2차원 그리드 맵이 주어지면 섬의 수를 센다. 섬은 물로 둘러싸여 있으며 인접한 토지를 수평 또는 수직으로 연결하여 형성됩니다. 그리드의 네 모서리가 모두 물로 둘러싸여 있다고 가정할 수 있습니다.
class Solution(object):
def numIslands(self, grid):
if len(grid) == 0 or len(grid[0]) == 0:
return 0
visited = [[False]*len(grid[0])]*len(grid)
count = 0
grid = [[int(k) for k in item] for item in grid]
for i in range(0, len(grid)):
for j in range(0, len(grid[0])):
if visited[i][j] == False and grid[i][j] == 1:
print('new island‑‑‑‑>', i, j)
count = count+1
self.dfs(grid, visited, i, j)
def dfs(self, grid, visited, i, j):
if i >= len(grid) or j >= len(grid[0]):
return
elif grid[i][j] == 0:
return
else:
visited[i][j] = True
self.dfs(grid, visited, i+1, j)
self.dfs(grid, visited, i, j+1)
어떤 이유에서인지 내가 방문한 행렬에는 각 dfs 호출 후에 전체 열이 true로 설정되어 있습니다. 여기에서 왜 그리고 무엇이 잘못되었는지 잘 모르겠습니다.
참조 솔루션
방법 1:
Note that multiplying a list creates multiple references to, not multiple copies of, the list in question. So [x] * 2 yields [x, x], not [copy.copy(x), copy.copy(x)], which is an important distinction if x is mutable. So when initializing visited, you'll want to use list comprehensions instead of list multiplication: [[False for _ in range(len(grid[0]))] for _ in range(len(grid))]. This will create a new list for each element.
Because False is immutable, you can get away with using multiplication for the inner lists ([[False] * len(grid[0]) for _ in range(len(grid))]), but it's probably better to get in the habit of the former.
(by Patricia Rozario、manveti)