문제

N*N의 섬나라 아일랜드의 지도가 격자판의 정보로 주어집니다. 각 섬은 1로 표시되어 상하좌 우와 대각선으로 연결되어 있으며, 0은 바다입니다. 섬나라 아일랜드에 몇 개의 섬이 있는지 구하는 프로그램을 작성하세요.

▣ 입력설명
첫 번째 줄에 자연수 N(3<=N<=20)이 주어집니다. 두 번째 줄부터 격자판 정보가 주어진다.

▣ 출력설명
첫 번째 줄에 섬의 개수를 출력한다.

▣ 입력예제 1
7
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
5

DFS 풀이

1. board를 전체 순회 한다. (2중 for 문)
2. board 내 좌표에서 1인 좌표를 찾으면 answer 값 증가
3. board의 i, j값 0으로 초기화 후 DFS 재귀 호출 진행
4. DFS 함수 내에서도 board의 x, y 값 0으로 초기화 (DFS 내에서 DFS 호출하는 경우도 존재)
5. 8방향(위, 우측 상단 대각선, 오른쪽, 우측 하단 대각선, 아래, 좌측 하단 대각선, 왼쪽, 좌측 상단 대각선) 으로 순회하여 이동 후 board 1인 값 다시 찾는다.
6. 만약 찾게 되면 DFS 다시 호출, 찾지 못한다면 종료
7. board를 모두 순회 할 때 까지 2-5 과정 반복

코드

function solution(board) {
  let answer = 0;
  // 8방향에 대한 dx, dy 설정
  let dx = [0, 1, 1, 1, 0, -1, -1, -1];
  let dy = [-1, -1, 0, 1, 1, 1, 0, -1];
  // board의 크기인 n 설정
  let n = board.length;
  function DFS(x, y) {
    // DFS 내에서 재귀 호출 되기 때문에 따로 board 값 초기화
    board[y][x] = 0;
    // 8방향으로 움직이며 만약 1인 값이 있다면 재귀 호출
    for (let k = 0; k < 8; k++) {
      let nx = x + dx[k];
      let ny = y + dy[k];
      // 만약 8방향으로 순회 하며 1인 값이 있다면 DFS 재귀 호출
      if (nx >= 0 && nx < n && ny >= 0 && ny < n && board[ny][nx] === 1) {
        DFS(nx, ny);
      }
    }
  }
  // board 전체 순회
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      // 만약 1인 좌표 찾을 경우 answer 1증가 후 board 내 좌표 값 0으로 초기화 후 DFS 함수 호출
      if (board[i][j] === 1) {
        answer++;
        board[i][j] = 0;
        DFS(j, i);
      }
    }
  }
  return answer;
}

console.log(
  solution([
    [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],
  ])
);

BFS 풀이

1. 좌표가 1인 지점을 찾을 경우 해당 좌표 값을 0으로 초기화 후 queue에 추가 한다.

2. 8방향으로 순회하며 만약 1인 좌표가 있을 경우 그 좌표들을 모두 queue에 추가 한다.

3. 만약 8방향을 순회했는데도 1인 좌표가 없다면 더 이상 queue에 추가하지 않게 되고 queue에 존재하지 않는다면 while문이 종료 된다.

board를 전체 순회하며 1인 좌표에 대해 다음과 같은 과정을 거치게 되면 답을 구할 수 있다.

코드

function solution(board) {
  let answer = 0;
  // 8방향에 대한 dx, dy 설정
  let dx = [0, 1, 1, 1, 0, -1, -1, -1];
  let dy = [-1, -1, 0, 1, 1, 1, 0, -1];
  // board의 크기인 n 설정
  let n = board.length;
  let queue = [];
  // board 순회
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      // 1인 좌표 찾을 경우 board[i][j] 0으로 초기화, queue에 [x,y] 좌표 push, answer 1증가
      if (board[i][j] === 1) {
        board[i][j] = 0;
        queue.push([j, i]);
        answer++;
        // queue 내 원소가 없을 때 까지 순회
        while (queue.length) {
          let [x, y] = queue.shift();
          // 8방향 순회
          for (let k = 0; k < 8; k++) {
            let nx = x + dx[k];
            let ny = y + dy[k];
            // 만약 8방향 중 1인 좌표가 있다면 board의 새로운 x,y 좌표 0으로 초기화 후 queue에 추가
            if (nx >= 0 && nx < n && ny >= 0 && ny < n && board[ny][nx] === 1) {
              board[ny][nx] = 0;
              queue.push([nx, ny]);
            }
          }
        }
      }
    }
  }
  return answer;
}

console.log(
  solution([
    [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],
  ])
);