Python Algorithm Q32

November 19, 2022

Q32 Number of Islands

참고사항

마지막 커밋이 언제였지… 아무튼 전역하고 오랜만에 글 올리기까지 거의 반년이상 지나서 문체랑 스타일이 뒤죽박죽일 것이다. 걍 내키는대로 작성하기로 결심!

Q

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Sample Input

Example 1

Input: grid = [
[“1”,”1”,”1”,”1”,”0”],
[“1”,”1”,”0”,”1”,”0”],
[“1”,”1”,”0”,”0”,”0”],
[“0”,”0”,”0”,”0”,”0”]
]
Output: 1

Example 2

Input: grid = [
[“1”,”1”,”0”,”0”,”0”],
[“1”,”1”,”0”,”0”,”0”],
[“0”,”0”,”1”,”0”,”0”],
[“0”,”0”,”0”,”1”,”1”]
] Output: 3

Constraints

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] is '0' or '1'.

1. My Own Try #1

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        sero = len(grid)
        garo = len(grid[0])
        discovered = [] #탐색 완료된 그리드 상의 좌표
        nums = 0

        def iteration(i: int, j: int):
            stack = [(i, j)]
            while stack:
                v = stack.pop()
                if v not in discovered:
                    discovered.append(v)
                    for tuples in [(v[0]-1, v[1]), (v[0]+1, v[1]), (v[0], v[1]-1), (v[0], v[1]+1)]:
                        if tuples[0] >= sero or tuples[0] < 0 or tuples[1] >= garo or tuples[1] < 0:
                            continue
                        if grid[tuples[0]][tuples[1]] == "0":
                            continue
                        if tuples in discovered: #이미 거친 얘가 중복해서 들어가지 않도록 필터링
                            continue
                        stack.append(tuples)
            return
    
        for i in range(sero): #세로 길이
            for j in range(garo): #가로 길이
                if grid[i][j] == "0" or (i,j) in discovered:
                    continue
                else: 
                    iteration(i,j)
                    nums += 1
        return nums

# test set
grid = [
  ["1","1","1","1","0"],
  ["1","1","0","0","0"],
  ["1","1","0","1","0"],
  ["0","0","1","0","1"]
]

a= Solution()
nums = a.numIslands(grid)
print(nums)

스택
discovered 집합 사용
결과 -> 타임아웃

DFS 푸는 두가지 방법(재귀, 스택) 중에서 가장 편하게 떠오르는 것이 스택이라서 스택으로 풀었더니 개같이 실패. 문제는 time-out이었다. 코드를 보면 알겠지만 for문, while문 이 두가지가 중첩되면서 boom한 것 같다.

2. My Own Try #2

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        sero = len(grid)
        garo = len(grid[0])
        discovered = [] #탐색 완료된 그리드 상의 좌표
        nums = 0

        def recursive(i: int, j: int):
            discovered.append((i,j))
            for tuples in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:
                if tuples[0] >= sero or tuples[0] < 0 or tuples[1] >= garo or tuples[1] < 0:
                    continue
                if grid[tuples[0]][tuples[1]] == "0":
                    continue
                if tuples in discovered:
                    continue
                recursive(tuples[0], tuples[1])
            return
    
        for i in range(sero): #세로 길이
            for j in range(garo): #가로 길이
                if grid[i][j] == "0" or (i,j) in discovered:
                    continue
                else: 
                    recursive(i,j)
                    nums += 1
        return nums

재귀
discovered 집합 사용
for문을 이용한 재귀(상하좌우)
결과 -> 타임아웃

재귀로 풀어본 버전. 근데 이것도 개같이 타임 초과… stack형식 자체가 문제가 아닌 것 같다. 근데 책 풀이 힐끗 보니까 재귀로 푼 버전 밖에 없던데 stack 자체가 문제일수도… 아무튼 아직 시간 복잡도를 늘리는 악성 코드들이 있나보다. 다시 시도

3. My Own Try #3

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        sero = len(grid)
        garo = len(grid[0])
        nums = 0

        def recursive(i: int, j: int):
            for tuples in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:
                if tuples[0] >= sero or tuples[0] < 0 or tuples[1] >= garo or tuples[1] < 0:
                    continue
                if grid[tuples[0]][tuples[1]] == "0":
                    continue
                grid[tuples[0]][tuples[1]] = '0'
                recursive(tuples[0], tuples[1])
            return
    
        for i in range(sero): #세로 길이
            for j in range(garo): #가로 길이
                if grid[i][j] == "0":
                    continue
                else: 
                    recursive(i,j)
                    nums += 1
        return nums

재귀
discovered 집합 사용 X
for문을 이용한 재귀(상하좌우)
결과 -> 성공!

#2번 풀이랑 무슨 차이가 있냐고? 바로 discovered 리스트 자체를 쓰지 않았다는 점이다. 책에 나와있는 정답 코드와 비교해봤을 때 가장 큰 문제점은 A in List 구분이 무려 2번이나 더 쓰였다는 점이다. for tuple문에서 if discovered -> continue 형식으로 한 번, 마지막에 if grid == 0 or in discovered 에서 두 번. linear한 구조였다면 그냥 O(+n)이었을 테지만, 하필 for문 안에 있었기 때문에 *n이 더 추가된 느낌? 그래서 discovered라는 함수를 쓰지 않고 지나간 영역을 확인하기 위해서, 쓸고 지나간 부분을 그냥 0으로 바꿔버리기로 했다(책에서 참고함). 이러니까 된다.

4. Given Solution #1

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        sero = len(grid)
        garo = len(grid[0])
        nums = 0

        def recursive(i: int, j: int):
            if i >= sero or i < 0 or j >= garo or j < 0:
                return
            if grid[i][j] == "0":
                return
            
            grid[i][j] = '0'
            
            recursive(i-1,j)
            recursive(i+1,j)
            recursive(i,j-1)
            recursive(i,j+1)
            
    
        for i in range(sero): #세로 길이
            for j in range(garo): #가로 길이
                if grid[i][j] == "0": #or (i,j) in discovered:
                    continue
                else: 
                    recursive(i,j)
                    nums += 1
        return nums

재귀
discovered 집합 사용 X
재귀 자체를 상하좌우에 대해서 각각 실행
결과 -> 성공!

책에 나와있던 풀이이다. #3번 풀이에서 시도했던 방식도 성공한 것을 보니까 for문을 써서 재귀하든, 재귀 자체를 네번 쓰든 상관없는 것 같다. 사실 시간복잡도가 달라질 것이 없기 때문에 크게 놀랄 일은 아니다. 이 문제의 핵심은 “discovered를 버리냐 아니냐”였던 것 같다. 거기서 time-out이 걸러지기 때문에…

Overall Review

아주 재밌었던 문제였다. DFS라는 개념을 처음 접해보고 풀어본 문제였기 때문에 신기했다. 문제 자체만 보고 “와 이거 사람이면 바로 맞출텐데 컴퓨터가 이걸 어떻게 이해하게 만들지” 싶었는데 역시 알고리즘의 힘은 대단한 것 같다… 다만 알고리즘 특정상 tree 구조를 반복해서 탐색하기 때문에 한두 끝 차이로 time-out이 걸릴 것 같아서 짤 때 시간 복잡도 낭비가 없도록 잘 짜야할 것 같다.

Hyuntae H