[LeetCode] #200. Number of Islands (Python)

문제

1인 부분은 땅으로 지나갈 수 있고, 0은 바다로 지나갈 수 없다. 땅/바다 정보가 들어있는 2차원 배열이 주어졌을 때, 총 섬의 개수를 구하여라. (문제 링크)

 

풀이 1

• 땅/바다 정보가 들어있는 지도 grid 를 탐색하면서 땅인 위치를 찾으면 해당 위치에서 4방향으로 땅이 있는지 dfs를 수행한다. dfs를 완료하면 연결된 땅을 다 방문했기 때문에 섬의 개수를 1 증가시킨다.
• dfs()를 살펴보면:
  • 탐색하는 좌표 (x, y)의 위치가 지도의 크기를 벗어나거나 이미 방문할 수 없는 곳(바다 또는 이미 방문한 곳)이면 종료한다.
  • 아래와 같이 탐색할 수 있는 조건으로 코드를 짤 수도 있다. 하지만 3개의 AND 조건을 확인하는 것 보다 OR 조건을 확인하는 시간이 짧아 탐색할 수 없는 조건을 사용했다.
  • 위의 조건에 걸리지 않아 탐색할 수 있는 위치라면 -1로 방문을 표시하고, 4방향으로 dfs를 호출한다.

def dfs(x, y):
    if 0<=x<len(grid) and 0<=y<len(grid[0]) and grid[x][y] == '1':
            grid[x][y] = '-1'
            dfs(x-1, y)
            dfs(x+1, y)
            dfs(x, y-1)
            dfs(x, y+1)

 

전체 코드는 아래와 같다.

# DFS 풀이, 중첩함수(nested function) 사용
class Solution1:
    def numIslands(self, grid: List[List[str]]) -> int:
        cnt = 0
        def dfs(x, y):
            if x<0 or x>=len(grid) or y<0 or y>=len(grid[0]) or grid[x][y] != '1':
                return        
            grid[x][y] = '-1'  # 방문 표시
            dfs(x-1, y)
            dfs(x+1, y)
            dfs(x, y-1)
            dfs(x, y+1)
        
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    dfs(i, j)
                    cnt += 1
        
        return cnt

 

풀이 2

- 풀이 1에서 dfs는 numIslands 안에 중첩 함수로 들어있다. dfs를 따로 꺼내

- 리트코드 풀이는 클래스로 선언되어 있어 dfs() 메서드의 첫 번째 인자로 self를 넣는다. 또한 두 메소드에서 grid 변수로 접근이 가능해야 하기 때문에 dfs()인자로 grid를 넘겨주었다. 

class Solution2:
    def dfs(self, grid, x, y):
        if x<0 or x>=len(grid) or y<0 or y>=len(grid[0]) or grid[x][y] != '1':
            return        
        grid[x][y] = '-1'  # 방문 표시
        self.dfs(grid, x-1, y)
        self.dfs(grid, x+1, y)
        self.dfs(grid, x, y-1)
        self.dfs(grid, x, y+1)
            
    def numIslands(self, grid: List[List[str]]) -> int:
        cnt = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    self.dfs(grid, i, j)
                    cnt += 1
        
        return cnt