200. Number of Islands

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

Number of Islands - LeetCode

Solution

class Solution:
    def __init__(self):
        self.m = 0
        self.n = 0
        self.grid = []
        self.visit = []
        
    def numIslands(self, grid):
        self.m = len(grid)
        self.n = len(grid[0])
        self.grid = grid
        self.visit = [[False] * self.n for _ in range(self.m)]
        ans = 0
        
        for i, row in enumerate(grid):
            for j, area in enumerate(row):
                if self.visit[i][j]:
                    continue
                if area == "0":
                    self.visit[i][j] = True
                    continue
                
                ans += 1
                self.chk(i, j)
        return ans

    def chk(self, i, j):
        self.visit[i][j] = True

        if j-1 >= 0 and not self.visit[i][j-1] and self.grid[i][j-1] == "1":
            self.chk(i, j-1)
        if j+1 < self.n and not self.visit[i][j+1] and self.grid[i][j+1] == "1":
            self.chk(i, j+1)
        if i-1 >= 0 and not self.visit[i-1][j] and self.grid[i-1][j] == "1":
            self.chk(i-1, j)
        if i+1 < self.m and not self.visit[i+1][j] and self.grid[i+1][j] == "1":
            self.chk(i+1, j)

• init을 만들고 변수를 선언해서, 다른 함수에서도 변수를 공유해서 사용하도록 하였다.
• 2중 for문으로 모든 요소를 확인한다.
• 방문한 곳이면 가지 않고, "0"이어도 가지 않는다.
• "1" 이라면, chk( ) 함수를 통해서 4방면을 확인한다.
• 범위를 체크하고, 방문한 곳인지 체크하고, "1"인지 체크한 후에 chk( )를 재귀로 다시 실행한다.
• 그렇게 한 땅에 이어진 모든 땅을 체크하면 for문으로 다시 돌아가고, 다른 땅을 찾는다.

 

• [[False] * self.n] * self.m
• 위 방법으로 2차원 배열을 선언하게 되면, 단순히 요소를 복사하게 되는 얕은복사 (shallow copy)가 일어난다. 단순히 요소를 복사하다 보니 바라보는 객체는 동일하다. 즉, 이러한 방식으로 선언 뒤에, 값을 변경하게되면 같은 열의 원소들도 값이 변경되는 현상이 발생하게 된다. 그래서 선언한 이후에 값을 변경하지 않는 경우에만 사용하는것이 좋다.

Another

class Solution:
    def numIslands(self, grid):
        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    self.dfs(grid, i, j)
                    count += 1
        return count

    def dfs(self, grid, i, j):
        if i<0 or j<0 or i>=len(grid) or j>=len(grid[0]) or grid[i][j] != '1':
            return
        grid[i][j] = '#'
        self.dfs(grid, i+1, j)
        self.dfs(grid, i-1, j)
        self.dfs(grid, i, j+1)
        self.dfs(grid, i, j-1)

• visit을 따로 두지 않고, 기존 grid에서 1을 방문하면 값을 바꾸도록 한다.
• 내 코드는 범위, 방문 여부, "1" 여부를 확인하고 함수로 들어갔다면, 여기는 일단 들어가고 확인한다.
• 확인하는 코드를 한 줄로 줄여서 코드가 더 간결해졌다.