41_countIslands

BFS로 풀 수 있는 기본 유형의 문제였다

const countIslands = function (grid) {
  if(grid.length===0) return 0;
  let n = grid.length;
  let m = grid[0].length;
  let vis = Array.from(Array(n), () => Array(m).fill(0)) //방문했는지를 나타내는 2차원배열
  let dx = [0,1,0,-1]; //상하좌우
  let dy = [1,0,-1,0]; //상하좌우
  let Q = []; //큐
  let count = 0; //섬의 개수

  for(let i=0;i<n;i++) {
    for(let j=0;j<m;j++) { //모든 좌표를 다 돌면서
      if(grid[i][j] === '0' || vis[i][j] === 1) continue; //물이나 이미 방문했으면 continue
      count++; //섬을 하나 찾았으므로 count++
      Q.push(i); //x좌표를 큐에 넣음
      Q.push(j); //y좌표를 큐에 넣음
      vis[i][j] = 1; //i,j는 방문했음
      while(Q.length > 0) { //큐에 아무것도 없을떄가지 와일문을 돌림
        let x = Q.shift(); //큐에 있던 x좌표
        let y = Q.shift(); //큐에 있던 y좌표
        for(let k=0;k<4;k++) {
          let cur_x = x + dx[k]; //상하좌우 x좌표
          let cur_y = y + dy[k]; //상하좌우 y좌표
          if(cur_x<0 || cur_x>=n || cur_y<0 || cur_y>=m) continue;
          if(grid[cur_x][cur_y] === '0' || vis[cur_x][cur_y] === 1) continue;
          Q.push(cur_x);
          Q.push(cur_y);
          vis[cur_x][cur_y] = 1;
        }
      }
    }
  }
  return count;
};