본문 바로가기
개발/알고리즘

[LeetCode] 200. Number of Islands (javascript)

by 자몬다 2021. 5. 31.
728x90

주어진 2차 배열에서 "1"은 육지, "0"은 바다를 나타낸다.

육지 덩어리의 갯수를 세는 문제다.

 

1을 찾고, 그 1에 상하좌우로 연결된 1들을 재귀함수로 모두 찾아내어 -1로 바꾸어준다.

한 덩어리를 다 바꾸고나면 count++를 해준다.

 

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function (grid) {
    const m = grid.length; // 4 max i
    const n = grid[0].length; // 5 max j
    let temp = grid;
    let index = findLandIndex(grid, m, n);
    let count = 0;
    while (index) {
        temp = checkFourWay(temp, index.i, index.j);
        index = findLandIndex(grid, m, n);
        count++;
    }
    return count;
};

const findLandIndex = (grid, m, n) => {
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] === '1') return { i, j };
        }
    }
};
const checkFourWay = (grid, i, j) => {
    grid[i][j] = -1;

    // top
    if (grid[i - 1] && grid[i - 1][j] === '1') {
        grid[i - 1][j] = -1;
        checkFourWay(grid, i - 1, j);
    }
    // down
    if (grid[i + 1] && grid[i + 1][j] === '1') {
        grid[i + 1][j] = -1;
        checkFourWay(grid, i + 1, j);
    }
    // left
    if (grid[i] && grid[i][j - 1] === '1') {
        grid[i][j - 1] = -1;
        checkFourWay(grid, i, j - 1);
    }
    //right
    if (grid[i] && grid[i][j + 1] === '1') {
        grid[i][j + 1] = -1;
        checkFourWay(grid, i, j + 1);
    }

    return grid;
};

https://leetcode.com/problems/number-of-islands/submissions/

댓글0