[JS] 코딩테스트 문제 : 섬나라 아일랜드 [BFS]

문제 : 섬나라 아일랜드(BFS 활용)

문제 설명

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

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

만약 위와 같다면

▣ 입력설명

첫 번째 줄에 자연수 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

내코드

function solution(board) {
  let answer = 0; // 섬 갯수
  let que = [];

  // 좌표기준 이동가능한 방향을 모두 저장해둔 배열 moveArr
  let moveArr = [
    [-1, -1], // 좌측 상단 방향
    [-1, 0], // 상단  방향향
    [0, -1], // 촤측  방
    [-1, 1], // 우측 상단 방향
    [0, 1], // 우측  방향
    [1, -1], // 좌측 하단 방향
    [1, 0], // 하단  방향
    [1, 1], // 우측 하단 방향
  ];

  // que 와 반복문을 활용해 연결된 섬이 있는지 확인하는 함수 BFS 선언
  function BFS(y, x) {
    answer++; // 새로운 섬 탐색을 시작했으므로 1 증가
    que.push([y, x]); // 현재 좌표를 que 에 등록
    board[y][x] = 0; // 방문여부 확인을 위해 현재 좌표의 값을 0 으로 초기화

    console.log(`새로운 섬탐색 시작!   좌표: [${y},${x}]`);
    while (que.length > 0) {
      let [curY, curX] = que.pop(); // 탐색할 섬 좌표하나를 꺼내 각각 curY, curX 에 저장

      // 이동할 수 있는 좌표를 전부 확인하기 위해 반복
      for (const [moveY, moveX] of moveArr) {
        const Y = curY + moveY; // 이동할 y 좌표 위치를 나타낼 변수 Y 선언
        const X = curX + moveX; // 이동할 x 좌표 위치를 나타낼 변수 X 선언

        // Y, X 값이 0 이상 board.length 미만인 경우 즉 이동할 수 있는 좌표만 확인
        if (Y >= 0 && Y < board.length && X >= 0 && X < board.length) {
          // 이동할 좌표에 이어진 섬이 있는 경우 이동한 위치좌표를 기준으로 추가 탐색을 위해 함수를 재귀적으로 호출
          if (board[Y][X] === 1) {
            console.log(`이어진 섬 발견! 좌표: [${Y},${X}]`);
            que.push([Y, X]); // que 에 이어진 섬 좌표 추가
            board[Y][X] = 0; // 발견한 섬은 확인을 위해 값을 0 으로 초기화
          }
        }
      }
    }

    console.log("------- 섬탐색 종료 -------");
  }

  for (let y = 0; y < board.length; y++) {
    for (let x = 0; x < board.length; x++) {
      if (board[y][x] === 1) BFS(y, x); // 새로운 섬 발견 좌표
    }
  }

  return answer;
}

let arr = [
  [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],
];

console.log(solution(arr));

풀이

1. 좌표 기준 이동 가능한 방향을 모두 저장해둔 2차원 배열 moveArr 선언
2. 연결된 섬이 있는지 확인을 위해 현재 좌표 값 y, x 를 인자로 가지는 BFS 선언
   a. 새로운 섬 탐색을 시작했으므로 발견한 섬 갯수를 의미하는 answer 변수를 1 증가
   함수 안에서 방문 여부 확인을 위해 현재 좌표의 값을 0 으로 초기화 하고 que 에 좌표값을 push
   b. que 좌표값이 존재 하지 않을 때까지 반복하는 반복문 안에서 탐색할 섬 좌표하나를 꺼내 각각 curY, curX 에 저장
   c. curY, curX 를 기준으로 moveArr 를 반복하면서 이동할 수 있는 좌표를 전부 확인 후 이어진 섬인 경우 que 에 이어진 섬 좌표를 추가하고 발견한 섬은 확인을 위해 값을 0 으로 초기화
   d. 반복문이 종료 즉 탐색이 끝난 후 함수 종료
3. 전체 섬 좌표를 2중 for 문으로 모두 탐색하면서 섬을 최초 발견할 경우 함수 BFS 를 호출하여 이어진 섬을 찾는 과정을 진행 최종적으로 모든 섬을 발견 후 종료

---

참고

https://www.inflearn.com/course/lecture?courseSlug=%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4&unitId=66593