*DFS란? Depth-first search의 약자로 깊이 우선 탐색하는 그래프 탐색 방법 중 하나이다.
자세한 내용은 [자료구조] 그래프(Graph) 참고.
200. 섬의 개수 (Number of Islands)
Example
- 주어진 2D 그리드 맵(m*n)에서 '1' 은 땅을 '0'은 물로 표현했을 때 섬의 개수를 출력하라.
Constraints
- m == grid.length
- n == grid[i].length
- 1 < m, n <= 300
- grid[i][j] is '0' or '1'
Solutions
Input: grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output: 1
- 4면이 모두 물('0') 인 육지('1')를 찾아야 함으로 네 방향을 각각 DFS 재귀를 이용해 탐색하는 방식으로 문제를 풀 수 있다.
- DFS 함수를 통해 땅이 아닐 때 까지 깊이 탐색한 후 탐색이 끝나면 count(섬의 개수) 를 1 증가시킨다. (재귀호출이 모두 끝나 빠져나오면 섬 하나를 반견한 것이다.)
- 한번 탐색한 곳은 마킹('v')을 통해 반복 탐색을 막는다.
코드 샘플
# Python
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
m = len(grid)
n = len(grid[0])
def dfs(i, j):
# 땅이 아닌 경우 종료
if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != '1':
return
# 탐색 여부 마킹
grid[i][j] = 'v'
# 4면 탐색
dfs(i + 1, j) # 아래
dfs(i - 1, j) # 위
dfs(i, j + 1) # 오른쪽
dfs(i, j - 1) # 왼쪽
count = 0
for i in range(m):
for j in range(n):
# 땅인 경우 4면 탐색을 시작한다.
if grid[i][j] == '1':
dfs(i, j)
# 모두 탐색 후 섬 개수 증가
count += 1
return count
// kotlin
class Solution {
fun numIslands(grid: Array<CharArray>): Int {
val m = grid.size
val n = grid[0].size
fun dfs(i: Int, j: Int) {
if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != '1') return
grid[i][j] = 'v'
dfs(i + 1, j)
dfs(i - 1, j)
dfs(i, j + 1)
dfs(i, j - 1)
}
var count = 0
for (i in 0..m-1) {
for (j in 0..n-1) {
if (grid[i][j] == '1') {
dfs(i, j)
count++
}
}
}
return count
}
}
실행결과
참조: 파이썬 알고리즘 인터뷰 https://github.com/onlybooks/algorithm-interview
'algorithm > problem solving' 카테고리의 다른 글
[리트코드 46] DFS를 활용한 순열 문제풀이 (0) | 2022.01.14 |
---|---|
[리트코드 17] DFS 탐색 문제풀이2 (0) | 2022.01.12 |
[리트코드 15] 투 포인터(Two Pointers) 를 활용한 문제풀이3 (0) | 2022.01.06 |
[리트코드 42] 투 포인터(Two Pointers) 를 활용한 문제풀이2 (0) | 2022.01.05 |
[리트코드 334] 투 포인터(Two Pointers) 를 활용한 문제풀이1 (0) | 2022.01.05 |