문제 풀이/leetcode
number of islands
by akatapata
2022. 1. 13.
- m x n 의 2차원 그리드
- "1" 은 land,"0"은 water를 의미
- 그리드 공간에서 islands(연결된 "1")의 개수 반환
solution
- dfs를 이용
- m x n 의 각 점들중 "1"인점 을 출발점으로 해서 도달가능한 모든점을 방문(dfs) 하고, 섬의개수 1증가 시키기
- 한번 방문한 점은 "0" 으로 표시
- grid 상에서 한 점(i,j)의 방문가능한 이웃한 점은 상하좌우에 위치하면서, 그리드 범위 이내이고 값이 "1" 인점
code
class Solution(object):
def numIslands(self, grid):
"""
:type grid: List[List[str]]
:rtype: int
"""
# m , n , dirs 초기화
m, n = len(grid), len(grid[0])
dirs = ((1,0),(0,1),(-1,0),(0,-1))
def _dfs(i,j):
grid[i][j]="0"
for _i,_j in dirs:
x,y = i+_i, j+_j
if 0 <= x < m and 0 <= y < n and grid[x][y]=="1":
_dfs(x,y)
num_islands = 0
for i in range(m):
for j in range(n):
# visit only land
if grid[i][j] == "1":
_dfs(i,j)
num_islands+=1
return num_islands