CS/알고리즘
[알고리즘_그래프] DFS(깊이 우선 탐색) 예제
하루살이
2022. 1. 23. 02:43
섬의 개수 문제: https://leetcode.com/problems/number-of-islands/
Number of Islands - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
Solution
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
def dfs(i, j):
# 땅이 아닌 경우 종료
if i < 0 or i >= len(grid) or \
j < 0 or j >= len(grid[0]) or \
grid[i][j] != '1':
return
# 이미 방문한 곳은 #으로 마킹
grid[i][j] = '#'
# 동서남북 탐색
dfs(i + 1, j)
dfs(i - 1, j)
dfs(i, j + 1)
dfs(i, j - 1)
count = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
# 육지인 경우
if grid[i][j] == '1':
# 탐색
dfs(i, j)
# 모든 육지 탐색 후 카운트 1 증가
count += 1
return count