[leetcode] number of islands - BFS/DFS

문제

Number of Islands 링크

완전 비슷한 유형의 문제!!
Programmers 네트워크 링크

1번째 풀이 -> DFS

class Solution:
    def numIslands(self, grid) -> int:
        global cnt
        # 동 남 서  북
        dr = [0, 1, 0, -1]
        dc = [1, 0, -1, 0]

        cnt = 0

        def dfs(c, r, depth):
            global cnt
            # base case -> grid 빠져나갔을 때, 물일 때
            if c>=col or r>=row or grid[c][r]=='0' or c<0 or r<0:
                return 
            # 이미 방문한 node 면
            if visited[c][r]==1:
                return

            # visited에 start_v 넣기
            visited[c][r]=1

            if depth==0:
                cnt+=1

            for i in range(4):
                nc, nr = c + dc[i], r + dr[i]
                dfs(nc, nr, depth+1)

        # initialize
        graph = {}
        col, row = len(grid), len(grid[0])
        visited = [[0] * row for _ in range(col)]

        for i in range(col):
            for j in range(row):
                dfs(i, j, 0)

        return cnt

개선해도 될 부분

for문을 모든 i, j에 대해서 돌기 때문에 비효율적이다.
for문을 돌지 않아도 되는 i, j는 어떨 때일까?

• 이미 visited 된 상태인 i,j OR
• water일 때

바꾸어 생각해보면, for문을 돌아야할 때는

• visited가 안된 i,j AND
• land 일때

개선된 코드 -> DFS

class Solution:
    def numIslands(self, grid) -> int:
        global cnt
        # 동 남 서  북
        dr = [0, 1, 0, -1]
        dc = [1, 0, -1, 0]

        cnt = 0

        def dfs(c, r):
            global cnt
            # base case -> grid 빠져나갔을 때, 물일 때
            if c>=col or r>=row or grid[c][r]=='0' or c<0 or r<0:
                return 
            # 이미 방문한 node 면
            if visited[c][r]==1:
                return

            # visited에 start_v 넣기
            visited[c][r]=1

            for i in range(4):
                nc, nr = c + dc[i], r + dr[i]
                dfs(nc, nr)

        # initialize
        graph = {}
        col, row = len(grid), len(grid[0])
        visited = [[0] * row for _ in range(col)]

        for i in range(col):
            for j in range(row):
                if grid[i][j] == "1" and visited[i][j] == 0:
                    cnt+=1                
                    dfs(i, j)

        return cnt

2번째 풀이 -> BFS

from collections import deque
class Solution:
    def numIslands(self, grid) -> int:
        
        col, row = len(grid), len(grid[0])
        visited = [[0] * row for _ in range(col)]
        
        cnt = 0
        def bfs(curr_c, curr_r):
                # E  S   W  N
            dc = [1, 0, -1, 0]
            dr = [0, 1, 0, -1]
            visited[curr_c][curr_r] = 1
            queue = deque()
            queue.append([curr_c, curr_r])
            
            while queue:
                temp = queue.popleft()
                for j in range(4):
                    next_c = temp[0] + dc[j]
                    next_r = temp[1] + dr[j]
                    # 가능한 부분만 방문처리
                    if (next_c>=0 and next_r>=0 and next_c<col and next_r<row):
                        if (grid[next_c][next_r] == '1' and not visited[next_c][next_r]):
                            visited[next_c][next_r] = 1
                            queue.append([next_c, next_r])
                
        for i in range(col):
            for j in range(row):
                if grid[i][j] == "1" and not visited[i][j]:
                    cnt+=1
                    bfs(i, j)
        return cnt

결과 확인 main function

if __name__ == "__main__":
    grid = [["1","0","1","1","0","1","1"]]
    solution = Solution()
    num_islands = solution.numIslands(grid)
    print("Number of islands:", num_islands)

결과!

Number of islands: 3