아일랜드 (BFS)

https://kong-dev.tistory.com/58

아일랜드(DFS)

같은 문제다.

이번엔 BFS로 풀어야 한다.

DFS로 하는건 못맞췄는데,

BFS는 맞췄다.

 

function solution(board) {
  let island = 0;
  const xmoving = [0, 1, 1, 1, 0, -1, -1, -1];
  const ymoving = [1, 1, 0, -1, -1, -1, 0, 1];
  const queue = [];

  for (let i = 0; i < board.length; i++) {
    for (let j = 0; j < board.length; j++) {
      if (board[i][j] === 1) {
        board[i][j] = 0;
        queue.push([i, j]);
        island++;

        while (queue.length) {
          const visited = queue.shift();
          const x = visited[0];
          const y = visited[1];

          for (let k = 0; k < xmoving.length; k++) {
            const nx = x + xmoving[k];
            const ny = y + ymoving[k];

            if (
              nx >= 0 &&
              nx < board.length &&
              ny >= 0 &&
              ny < board.length &&
              board[nx][ny] === 1
            ) {
              board[nx][ny] = 0;
              queue.push([nx, ny]);
            }
          }
        }
      }
    }
  }
  return island;
}

... 어케 풀었누...

 

찬찬히 다시보자.

function solution(board) {
  let island = 0;
  const xmoving = [0, 1, 1, 1, 0, -1, -1, -1];
  const ymoving = [1, 1, 0, -1, -1, -1, 0, 1];
  const queue = [];

  return island;
}

 

island는 카운터

xmoving, ymoving은 같은 인덱스의 값을 조합하면 

이동할 방향이 된다.

12시부터 시계방향으로 8방향이다.

빈배열 queue를 만들었다.

여기다 넣었다 뺐다를 할거다.

 

function solution(board) {
  let island = 0;
  const xmoving = [0, 1, 1, 1, 0, -1, -1, -1];
  const ymoving = [1, 1, 0, -1, -1, -1, 0, 1];
  const queue = [];

  for (let i = 0; i < board.length; i++) {
    for (let j = 0; j < board.length; j++) {
      if (board[i][j] === 1) {
        board[i][j] = 0;
        queue.push([i, j]);
        island++;

       }
    }
  }
  return island;
}

이중 for문을 돌려서

지도에서 1을 발견하면 발견한 곳의 

좌표값을 i,j로 받고, 0으로 변경한다.

그리고 i, j값을 배열로 만들어 queue에다 넣고

카운터에 1을 더해준다.

 

function solution(board) {
  let island = 0;
  const xmoving = [0, 1, 1, 1, 0, -1, -1, -1];
  const ymoving = [1, 1, 0, -1, -1, -1, 0, 1];
  const queue = [];

  for (let i = 0; i < board.length; i++) {
    for (let j = 0; j < board.length; j++) {
      if (board[i][j] === 1) {
        board[i][j] = 0;
        queue.push([i, j]);
        island++;

        while (queue.length) {
          const visited = queue.shift();
          const x = visited[0];
          const y = visited[1];

         }
      }
    }
  }
  return island;
}

queue.length가 0이 될때 까지 while문을 반복한다.

queue에서 shift로 빼낸 값을 visited에 할당하고

visited의 0번째 값과 1번째 값을 각각 x, y 에 할당해준다.

 

 

function solution(board) {
  let island = 0;
  const xmoving = [0, 1, 1, 1, 0, -1, -1, -1];
  const ymoving = [1, 1, 0, -1, -1, -1, 0, 1];
  const queue = [];

  for (let i = 0; i < board.length; i++) {
    for (let j = 0; j < board.length; j++) {
      if (board[i][j] === 1) {
        board[i][j] = 0;
        queue.push([i, j]);
        island++;

        while (queue.length) {
          const visited = queue.shift();
          const x = visited[0];
          const y = visited[1];

          for (let k = 0; k < xmoving.length; k++) {
            const nx = x + xmoving[k];
            const ny = y + ymoving[k];

           }
        }
      }
    }
  }
  return island;
}

 

for문을 통해 현재 위치에서 이동할 여덟방향을

xmoving과 ymoving을 이용해 각각 nx와 ny에 할당해준다.

function solution(board) {
  let island = 0;
  const xmoving = [0, 1, 1, 1, 0, -1, -1, -1];
  const ymoving = [1, 1, 0, -1, -1, -1, 0, 1];
  const queue = [];

  for (let i = 0; i < board.length; i++) {
    for (let j = 0; j < board.length; j++) {
      if (board[i][j] === 1) {
        board[i][j] = 0;
        queue.push([i, j]);
        island++;

        while (queue.length) {
          const visited = queue.shift();
          const x = visited[0];
          const y = visited[1];

          for (let k = 0; k < xmoving.length; k++) {
            const nx = x + xmoving[k];
            const ny = y + ymoving[k];

            if (
              nx >= 0 &&
              nx < board.length &&
              ny >= 0 &&
              ny < board.length &&
              board[nx][ny] === 1
            ) {
              board[nx][ny] = 0;
              queue.push([nx, ny]);
            }
          }
        }
      }
    }
  }
  return island;
}

 

board[nx][ny]가 지도밖을 벗어나지 않고,

값이 1이라면,

즉시 값을 0으로 할당해준다.

이렇게 해줘야 중복되는 값이 queue로 들어 가지 않는다.

nx와 ny를 배열로 만들어서 queue에다 push 해주면

다시 queue.length가 truthy한 값으로 돼서

while문이 반복된다.