<--- 리트코드 200. Number of Islands --->
# 문제: 1을 육지로, 0을 물로 가정한 2D 그리드 맵이 주어졌을 때, 섬의 개수를 계산하라.
입력
| 11110 11010 11000 00000 |
출력
| 1 |
입력
| 11000 11000 00100 00011 |
출력
| 1 |
# 풀이
1. DFS로 그래프 탐색
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
def num_islands(grid):
if not grid:
return 0
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] = 0
# 동서남북 탐색
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
grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"],
]
print(num_islands(grid))
|
cs |
'Python' 카테고리의 다른 글
| 파이썬 알고리즘 인터뷰 - 34. 순열 (0) | 2022.01.30 |
|---|---|
| 파이썬 알고리즘 인터뷰 - 33. 전화 번호 문자 조합 (0) | 2022.01.30 |
| 파이썬 알고리즘 인터뷰 - 31. 상위 K 빈도 요소 (0) | 2022.01.27 |
| 파이썬 알고리즘 인터뷰 - 30. 중복 문자 없는 가장 긴 부분 문자열 (0) | 2022.01.27 |
| 파이썬 알고리즘 인터뷰 -29. 보석과 돌 (0) | 2022.01.25 |