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

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

문제 설명

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; // 섬 갯수

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

  // 연결된 섬이 있는지 확인을 위한 재귀 함수 DFS 선언
  function DFS(y, x) {
    board[y][x] = 0; // 방문여부 확인을 위해 현재 좌표의 값을 0 으로 초기화

    // 이동할 수 있는 좌표를 전부 확인하기 위해 반복
    for (const [moveY, moveX] of moveArr) {
      const Y = y + moveY; // 이동할 y 좌표 위치를 나타낼 변수 Y 선언
      const X = x + 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}]`);
          DFS(Y, X);
        }
      }
    }
  }

  // 2중 for 문으로 전체 배열 순회
  for (let i = 0; i < board.length; i++) {
    for (let j = 0; j < board.length; j++) {
      // 현재 좌표에 섬이 있다면 현재 좌표로 DFS 함수 호출
      if (board[i][j] === 1) {
        answer++; // 섬 발견했으므로 answer 1 증가
        console.log(`새로운 섬탐색 시작!   좌표: [${i},${j}]`);
        DFS(i, j);
        console.log("------- 섬탐색 종료 -------");
      }
    }
  }

  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 를 인자로 가지는 재귀 함수 DFS 선언
   • 함수 안에서 방문 여부 확인을 위해 현재 좌표의 값을 0 으로 초기화하고 moveArr 를 반복하면서 이동할 수 있는 좌표를 전부 확인
   • 만약 이동할 좌표에 이어진 섬이 있는 경우 이동한 위치 좌표를 기준으로 추가 탐색을 위해 함수 DFS 를 재귀적으로 호출
3. 2중 for 문으로 배열 순회하며 좌표에 섬이 있다면 현재 좌표로 DFS 함수 호출

보완할 수 있는 부분

// 기존코드
let  moveArr  = [
    [-1, -1], // 좌측 상단 방향
    [-1, 0], // 상단 방향향
    [0, -1], // 촤측 방
    [-1, 1], // 우측 상단 방향
    [0, 1], // 우측 방향
    [1, -1], // 좌측 하단 방향
    [1, 0], // 하단 방향
    [1, 1], // 우측 하단 방향
];
...
for (const [moveY, moveX] of  moveArr) {
    const Y = y + moveY;
    const X = x + moveX;
    ...
}

// 보완코드
let dx=[-1, -1, 0, 1, 1, 1, 0, -1];
let dy=[0, 1, 1, 1, 0, -1, -1, -1];
...
for(let k=0; k<8; k++){
    let nx=x+dx[k];
    let ny=y+dy[k];
    ...
}

코드 컨벤션 때문에 2차원 배열 선언 부분이 길어질 수 있으므로 배열 두개로 선언해 선언 부분을 2줄로 줄일 수 있음

---

참고

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=64157