[리트코드][파이썬] Number of Islands ✅

문제

Number of Islands - LeetCode

 

접근 방법

1.한 칸씩 확인한다.→ 이중for문

2.육지의 경우 주변을 다 탐색한다. → bfs or dfs

3.탐색한 육지는 다시 탐색하지 않도록 기록한다. →visited=True

4.탐색을 완료했다는 것은 섬 하나를 탐색했다는 것으로 탐색 후 카운트+=1 한다. →count+=1

 

코드

BFS풀이

from collections import deque
import sys

def numIslands(grid):
  
    r, c = len(grid), len(grid[0])
    visited = [[False]*c for _ in range(r)]
   
    def bfs(x,y):
        dx = [-1,1,0,0]
        dy = [0,0,-1,1]

        visited[x][y] = True #1.visit처리
        queue = deque()
        queue.append((x,y)) #1.큐 초기화
        while queue:
            cur_x, cur_y =queue.popleft()  #2.popleft
            for i in range(4):      
                next_x = cur_x + dx[i]
                next_y = cur_y + dy[i]     #2.열결된 정점 확인 for문
                if next_x >=0 and next_x < r and next_y >=0 and next_y < c:
                    if grid[next_x][next_y] == "1" and not visited[next_x][next_y]: #3.조건부합확인
                        visited[next_x][next_y]=True  #3.visit처리
                        queue.append((next_x,next_y))  #3.q처리
                        
    count = 0 
    for i in range(r):
        for j in range(c):
            if grid[i][j] == "1" and not visited[i][j]:
                bfs(i,j)
                count +=1


    return count





print(numIslands(grid=[
    ["1","1","0","0","0"],
    ["1","1","0","0","0"],
    ["0","0","1","0","0"],
    ["0","0","0","1","1"]]))#답:3


#n = int(sys.stdin.readline().strip())
#area= [list(map(int,sys.stdin.realine().strip().split())) for _ in range(n)]
#visited = [[0 for _ in range(n)] for _ in range(n)]#n*n

DFS 풀이

def numIslands(grid):

    r, c = len(grid), len(grid[0])
    visited = [[False]*c for _ in range(r)]
    def dfs(i, j):
        if i < 0 or i >= r or j < 0 or j >= c or grid[i][j] == '0' or visited[i][j]:
            return
        visited[i][j] = True
        dfs(i + 1, j)
        dfs(i - 1, j)
        dfs(i, j + 1)
        dfs(i, j - 1)

    count = 0
    for i in range(r):
        for j in range(c):
            if grid[i][j] == "1" and not visited[i][j]:
                dfs(i, j)
                count += 1
    return count




print(numIslands(grid=[
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]])) 답:3

 

 

 

🌟