(Leet Code JS)Island Perimeter

463. Island Perimeter

 

You are given row x col grid representing a map where grid[i][j] = 1 represents land and grid[i][j] = 0 represents water.

Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells).

The island doesn't have "lakes", meaning the water inside isn't connected to the water around the island. One cell is a square with side length 1. The grid is rectangular, width and height don't exceed 100. Determine the perimeter of the island.

 

Example 1:

Input: grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]] Output: 16 Explanation: The perimeter is the 16 yellow stripes in the image above.

Example 2:

Input: grid = [[1]] Output: 4

Example 3:

Input: grid = [[1,0]] Output: 4

 

Constraints:

• row == grid.length
• col == grid[i].length
• 1 <= row, col <= 100
• grid[i][j] is 0 or 1.

BFS가 훨씬 쉬워 보이지만 카테고리가 DFS로 걸려있으니 DFS로 풀어보았다!

 

우선 탐색할 방향을 나타내는 directX와 directY.

주어진 grid의 가로 길이 = row, 세로 길이 = col.

방문 여부를 나타내는 visited.

정답을 나타내는 sum을 변수로 선언했다.

 

그리고 2개의 함수를 이용해 정답을 찾아내면 된다.

 

checkRange는 탐색할 좌표의 범위가 유효한지 알 수 있는 함수.

dfs는 탐색을 진행하는 함수.

 

-->탐색 시작.

이중 for문을 이용해 가장 처음 땅인 부분을 찾아낸다.

해당 좌표의 방문 여부를 true로 바꿔준 후, dfs를 시작.

 

dfs() 함수.

1) 4방향을 검사해야 하기 때문에 for문을 실행하여, 4방향을 검사한다.

 

2) 만약 새로운 좌표가 row와 col 범위에 맞는지 검사한다.

 

2-1) 범위에 맞다면 새로운 좌표가 땅인지 물인지 검사하도록 한다.

  2-1-1) 새로운 좌표가 땅이면서 한번도 방문하지 않은 좌표라면, 새로운 좌표의 방문 여부를 true로 바꿔주고 새로운
          좌표로 1)부터 진행한다.

  2-1-2) 새로운 좌표가 물이라면 sum++.

 

2-2) 범위를 벗어나게 된다면 sum++을 해준다.

 

이렇게 하면 답을 자동으로 찾을 수 있다!

/**
 * @param {number[][]} grid
 * @return {number}
 */
const islandPerimeter = (grid) => {
    const directX = [-1, 1, 0, 0];
    const directY = [0, 0, -1, 1]; 
    const row = grid.length;
    const col = grid[0].length;
    const visited = Array.from({length: row}, () => Array(col).fill(false));
    let sum = 0;
    
    const checkRange = (x, y) => x >= 0 && x < row && y >= 0 && y < col ? true : false;
    
    const dfs = (x, y) => {
        for(let i = 0; i < 4; i++){
            const nx = x + directX[i];
            const ny = y + directY[i];
            
            if(checkRange(nx, ny)){
                if(grid[nx][ny] && !visited[nx][ny]){
                    visited[nx][ny] = true;
                    dfs(nx, ny);
                } else if(!grid[nx][ny]){
                    sum++;
                }
            } else{
                sum++;
            }
        }
    }
    
    for(let i = 0; i < row; i++){
        for(let j = 0; j < col; j++){
            if(grid[i][j] && !visited[i][j]){
                visited[i][j] = true;
                dfs(i, j);
            }
        }
    }
    
    return sum;
};