비선형 자료구조_1. Number of Islands
leetcode 200. Number of Islands
문제
1을 육지로, 0을 물로 가정한 2D 그리드 맵에서 섬의 개수를 구하라.
입출력예시
- 입력:
11110
11010
11000
00000
- 출력: 1
풀이
그리드 맵을 동서남북이 연결된 그래프로 가정하고 DFS 재귀를 이용해 그래프 탐색을 한다.
파이썬
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] = 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
- runtime: 136 ms
- memory: 15.6 MB
자바스크립트
const numIslands = function(grid) {
const dfs = (i, j) => {
if (i < 0 || i >= grid.length ||
j < 0 || j >= grid[i].length ||
grid[i][j] !== '1') {
return;
}
grid[i][j] = '0';
dfs(i + 1, j) // down
dfs(i - 1, j) // up
dfs(i, j + 1) // right
dfs(i, j - 1) // left
}
let count = 0;
for (let i = 0; i < grid.length; i++) {
for(let j = 0; j < grid[i].length; j++) {
if(grid[i][j] === '1') {
count++;
dfs(i, j)
}
}
}
return count;
};
- runtime: 96 ms
- memory: 39.7 MB
참고
파이썬 알고리즘 인터뷰
Author And Source
이 문제에 관하여(비선형 자료구조_1. Number of Islands), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@sy3783/비선형1.-Number-of-Islands저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)