_(1).jpeg&blockId=0e552736-74f0-4f5a-89e1-328d4931ca7c)
문제
Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
Input: grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output: 1
Plain Text
복사
Example 2:
Input: grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Output: 3
Plain Text
복사
Constraints:
•
m == grid.length
•
n == grid[i].length
•
1 <= m, n <= 300
•
grid[i][j] is '0' or '1'.
해석
grid는 이중배열로 표현된 암묵적 그래프이다. 문제를 해석하면 1은 육지이고 0은 물이다. 이 그래프에서 가로, 세로로 인접한 육지를 하나의 섬으로 보고, grid 안에 섬이 총 몇 개 있는지 구하는 문제이다.
풀이
bfs
bfs는 시작 노드에서 가까운 노드들부터 먼저 방문한다. dfs가 이어진 곳 끝까지 방문한 뒤 다른 인접 노드를 방문하는 것과는 다르다. dfs는 재귀를 이용하지만 bfs는 queue를 사용해 인접 노드부터 순서대로 방문한다.
/**
* @param {character[][]} grid
* @return {number}
*/
var numIslands = function(grid) {
const row = grid.length
const col = grid[0].length
const visited = Array.from({length: row}, () => Array(col).fill(false))
const directions = [[1,0],[0,1],[-1,0],[0,-1]]
const bfs = (x, y) => {
const queue = []
queue.push([x,y])
visited[x][y] = true
while(queue.length > 0) {
const [prevX, prevY] = queue.shift()
for ([offsetX, offsetY] of directions) {
const nextX = prevX + offsetX
const nextY = prevY + offsetY
const inRange = nextX < row && nextY < col && nextX >= 0 && nextY >= 0
if (inRange && !visited[nextX][nextY] && grid[nextX][nextY] === '1') {
visited[nextX][nextY] = true
queue.push([nextX, nextY])
}
}
}
}
let answer = 0
for(let i=0;i<row;i++) {
for(let j=0;j<col;j++) {
if (grid[i][j]==='1' && !visited[i][j]) {
bfs(i, j)
answer++
}
}
}
return answer
};
JavaScript
복사
우선 grid의 크기를 파악한 뒤, 동일한 크기의 visited 배열을 생성하여 특정 위치를 이미 방문했는지 여부를 저장한다. 이후, 상하좌우 네 방향으로 탐색할 수 있도록 방향 벡터 directions를 정의하고, bfs 탐색 함수 bfs를 작성한다.
bfs 함수에서는 큐를 초기화하고, 시작 지점을 큐에 삽입한 뒤 방문 처리한다. 이후 큐가 빌 때까지 루프를 돌며 현재 위치에서 인접한 네 방향을 확인하고, 아직 방문하지 않았으며 값이 '1'인 위치를 큐에 추가하면서 동시에 방문 처리한다. 이 과정을 반복하면 시작 지점에서 연결된 모든 '1'을 방문하게 된다.
중요한 점은 큐에 좌표를 삽입할 때 바로 방문 처리를 해야 한다는 점이다. 큐에서 꺼낸 이후에 방문 처리를 하면 동일한 좌표가 중복으로 큐에 들어가 불필요한 연산이 반복될 수 있으며, 이는 성능 저하로 이어진다. 특히 섬의 크기가 크고 복잡한 테스트 케이스에서는 이로 인해 시간 초과가 발생할 수 있다. 따라서 bfs에서는 큐에 넣는 순간 바로 visited를 true로 설정하는 것이 좋다.
이제 전체 grid를 순회하면서 아직 방문하지 않았고 값이 '1'인 지점을 발견하면 bfs를 시작한다. bfs가 끝났다는 것은 하나의 섬 전체를 모두 방문한 것이므로, 이때 섬의 개수를 카운트하는 answer 값을 증가시킨다. 이 과정을 전체 배열에 대해 반복한 후, 최종적으로 구한 answer 값을 반환하면 전체 섬의 개수를 얻을 수 있다.
dfs
/**
* @param {character[][]} grid
* @return {number}
*/
var numIslands = function(grid) {
const row = grid.length
const col = grid[0].length
const visited = Array.from({length: row}, () => Array(col).fill(false))
const directions = [[1,0],[0,1],[-1,0],[0,-1]]
const dfs = (x, y) => {
for ([offsetX, offsetY] of directions) {
const nextX = x + offsetX
const nextY = y + offsetY
const inRange = nextX >= 0 && nextY >= 0 && nextX < row && nextY < col
if (inRange && !visited[nextX][nextY] && grid[nextX][nextY] === '1') {
visited[nextX][nextY] = true
dfs(nextX, nextY)
}
}
}
let answer = 0
for(let i=0;i<row;i++) {
for(let j=0;j<col;j++) {
if (grid[i][j]==='1' && !visited[i][j]) {
dfs(i, j)
answer++
}
}
}
return answer
};
JavaScript
복사
dfs에서는 재귀를 이용한다는 점만 제외하면 bfs의 풀이 방식과 비슷하다. dfs 함수는 현재 위치에서 4방향으로 이동할 수 있는 모든 좌표를 계산한 뒤, 해당 좌표가 배열의 범위 안에 있고 아직 방문하지 않았으며 '1'이라면, 해당 위치를 방문 처리한 후 재귀적으로 다시 dfs를 호출한다. 이렇게 하면 연결된 모든 '1'들을 탐색할 수 있다.
전체 grid를 순회하면서 아직 방문하지 않았고 값이 '1'인 위치를 찾으면, 그 지점에서 dfs를 시작한다. dfs가 끝났다는 것은 해당 지점에서 연결된 섬 하나 전체를 모두 방문했다는 의미이므로, 섬의 개수를 나타내는 answer 값을 1 증가시킨다. 이 과정을 전체 배열에 대해 반복한 후, answer 값을 반환하면 섬의 총 개수를 구할 수 있다.
