아일랜드(DFS)

 

문제설명

[1, 1, 0, 0, 0, 1, 0],

[0, 1, 1, 0, 1, 1, 0],

[0, 1, 0, 0, 0, 0, 0],

[0, 0, 0, 1, 0, 1, 1],

[1, 1, 0, 1, 1, 0, 0],

[1, 0, 0, 0, 1, 0, 0],

[1, 0, 1, 0, 1, 0, 0],

 

1은 섬이고 0은 바다다.

섬은 상하좌우 그리고 대각선으로도 연결 돼 있고

이어진 섬은 하나로 친다.

섬의 갯수를 구하라

 

접근방법

설명이 너무 대충인가.

DFS를 이용해서 풀어야 한다.

우선 이중for 문을 이용해서 1을 찾는다.

1을 찾으면  카운트를 하고,

DFS함수를 호출한다.

DFS함수 내부는 1을 만난 지점을 0으로 바꾸고 

팔방으로 1이 있는지 확인한다.

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];

  function DFS(x, y) {
    board[x][y] = 0;
    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
      ) {
        DFS(nx, ny);
      }
    }
  }

  for (let i = 0; i < board.length; i++) {
    for (let j = 0; j < board.length; j++) {
      if (board[i][j] === 1) {
        console.log(i, j);
        island++;
        DFS(i, j);
      }
    }
  }

  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];

    return island;
}

island는 카운터다.

섬을 발견하면 숫자를 하나씩 늘려줄거다.

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

이동하는 방향 8개가 나온다

12시부터 시계방향이다.

 

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];


  for (let i = 0; i < board.length; i++) {
    for (let j = 0; j < board.length; j++) {
      if (board[i][j] === 1) {
        console.log(i, j);
        island++;
        DFS(i, j);
      }
    }
  }

  return island;
}

 

마지막 문단의 이중for문이다.

board즉 지도에 i, j를 0부터 넣어서

1이 있는지 확인한다.

1이 을 만나면 카운트를 하나 늘리고

DFS함수를 실행한다.

 

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];

  function DFS(x, y) {
    board[x][y] = 0;
    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
      ) {
        DFS(nx, ny);
      }
    }
  }

  for (let i = 0; i < board.length; i++) {
    for (let j = 0; j < board.length; j++) {
      if (board[i][j] === 1) {
        console.log(i, j);
        island++;
        DFS(i, j);
      }
    }
  }

  return island;
}

 

마지막 DFS함수다.

이중for문에서 보낸 i,j값을 x,y 로 받고

우선 지도의 x,y좌표에 해당하는 곳을 0으로 만든다.

그리고 for 문으로 xmoving과 ymoving을 조합해

nx와 ny를 구한다.

board[nx][ny]가 지도 밖으로 나가지 않고,

1이라면 재귀함수를 호출해

반복한다.