leetCode - Number of Islands

leetcode.com/problems/number-of-islands/

 

시간 복잡도가 높은 풀이

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
    
    	# pseudo code
        """
        def DFS(v)
            v <- "2" (mark)
            for w in every "1" adjacent(NSEW) to v:
                DFS(w)
        count = 0
        for x in every "1" in grid:
            DFS(x)
            count += 1
        return count
        """
        
        count = 0
        while True:
            x = self.find_one(grid)
            if x == (-1, -1):
                break
            self.DFS(grid, x)
            count += 1
        return count
    
    
    
    def DFS(self, grid: List[List[str]], v: tuple):
        R, C = len(grid), len(grid[0])
        r, c = v
        grid[r][c] = "2"
        
        # search every "1" adjacent to v
        adjacents = []
        if r - 1 >= 0 and grid[r - 1][c] == "1": 
            adjacents.append((r - 1, c))
        if r + 1 < R and grid[r + 1][c] == "1":
            adjacents.append((r + 1, c))
        if c - 1 >= 0 and grid[r][c - 1] == "1": 
            adjacents.append((r, c - 1))
        if c + 1 < C and grid[r][c + 1] == "1": 
            adjacents.append((r, c + 1))
        
        for adjacent in adjacents:
            self.DFS(grid, adjacent)
            
        
        
    def find_one(self, grid: List[List[str]]) -> tuple:
        for r, row in enumerate(grid):
            for c, elem in enumerate(row):
                if elem == "1":
                    return (r, c)
        return (-1, -1)
                

 

이 코드에서는 하나의 섬을 찾고 다른 섬을 찾을 때 비효율적으로 다시 처음부터 1이 나올 때까지 브루트 포스로 찾는 방식을 택했다.(find_one()) -> O(n^2)

 

그 대신 이렇게 하는게 바람직하다.

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
    
    	# pseudo code
        """
        def DFS(v)
            v <- "2" (mark)
            for w in every "1" adjacent(NSEW) to v:
                DFS(w)
        count = 0
        for x in every "1" in grid:
            DFS(x)
            count += 1
        return count
        """
        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == "1":
                    count += 1
                    self.DFS(grid, (i, j))
        return count
    
    
    def DFS(self, grid: List[List[str]], v: tuple):
        R, C = len(grid), len(grid[0])
        r, c = v
        grid[r][c] = "2"
        
        # search every "1" adjacent to v
        adjacents = []
        if r - 1 >= 0 and grid[r - 1][c] == "1": 
            adjacents.append((r - 1, c))
        if r + 1 < R and grid[r + 1][c] == "1":
            adjacents.append((r + 1, c))
        if c - 1 >= 0 and grid[r][c - 1] == "1": 
            adjacents.append((r, c - 1))
        if c + 1 < C and grid[r][c + 1] == "1": 
            adjacents.append((r, c + 1))
        
        for adjacent in adjacents:
            self.DFS(grid, adjacent)

                

-> O(n)

 

또 개선책으로

 

1. grid를 멤버 변수로

2. adjacents를 찾는 대신 "1"이 아니거나 범위에서 벗어나면 바로 리턴하는 방식으로 DFS를 짜면

 

더 깔끔해진다.

 

하지만 2번은 코드는 깔끔해지지만 호출 횟수가 위 코드보다 훨씬 많기 때문에 훨씬 오래 걸렸다.