Number of Islands
문제 Link
https://leetcode.com/problems/number-of-islands/ (opens in a new tab)
문제 해설
전체 그래프를 다 BFS/DFS하는게 아니라 1인 부분만 BFS해서 BFS 함수가 수행된 횟수 == 섬의 개수가 되는게 핵심이다.
from collections import deque
class Solution:
def numIslands(self, grid: list[list[str]]) -> int:
ori_row, ori_col = len(grid), len(grid[0])
visited = [[False for _ in range(ori_col)] for _ in range(ori_row)]
ans = 0
def bfs(row, col) :
dx = [-1,1,0,0]
dy = [0,0,1,-1]
visited[row][col] = True
q = deque()
q.append((row, col))
while q :
cur_row, cur_col = q.popleft()
for i in range(len(dx)) :
next_row = cur_row + dx[i]
next_col = cur_col + dy[i]
if next_row >= 0 and next_row < ori_row and next_col >= 0 and next_col < ori_col :
if not visited[next_row][next_col] and grid[next_row][next_col] == "1" :
visited[next_row][next_col] = True
q.append((next_row, next_col))
for i in range(ori_row) :
for j in range(ori_col) :
if not visited[i][j] and grid[i][j] == "1" :
bfs(i, j)
ans += 1
return ans