[DFS/BFS]섬나라 아일랜드

문제

 

문제풀이

https://choi95.tistory.com/126

[DFS]미로 탐색

해당 문제는 이전에 포스팅 했던 미로 탐색 문제와 매우 유사하지만 다음과 같은 차이점이 있다.

1. 탐색 방향이 '좌 우 상 하' 외에도 대각선까지 포함되어야 한다.
2. 여러 갈래의 길을 구하는 미로 탐색은 한번 탐색했던 길을 갔던 지점으로 체크한 뒤에 백트래킹을 할 경우를 대비해 다시 재귀 호출을 마친 뒤에 가지 않았음으로 초기화 해주지만 해당 문제에서는 정해져 있는 섬을 구하는 것이기 때문에 한번 탐색한 지점은 그대로 갔던 지점으로 둔다(무한 루프 방지)

코드

function solution(board) {
  let answer = 0;
  let n = board.length;
  let dx = [-1, -1, 0, 1, 1, 1, 0, -1]; //시계 방향 순서대로(대각선 좌표까지 포함)
  let dy = [0, 1, 1, 1, 0, -1, -1, -1];
  let m = dx.length;

  function DFS(x, y) {
    board[x][y] = 0; //무한 루프 방지 및 한번 참조한 섬을 다시 참조하지 않게끔 0으로 초기화
      for(let k = 0; k < m; k++) {
        let nx = x + dx[k];
        let ny = y + dy[k];
        if(nx >= 0 && nx < n && ny >= 0 && ny < n && board[nx][ny] === 1) {
          DFS(nx, ny);
        }
      }
  }

  for(let i = 0; i < n; i++) {
    for(let j = 0; j < n; j++) {
      if(board[i][j] === 1) {
        answer++; 
        DFS(i, j);
      }
    }
  }

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

 

코드_BFS 활용

function solution(board) {
  let answer = 0;
  let n = board.length;
  let dx = [-1, -1, 0, 1, 1, 1, 0, -1];
  let dy = [0, 1, 1, 1, 0, -1, -1, -1];
  let m = dx.length;
  let queue = [];

  for(let i = 0; i < n; i++) {
    for(let j = 0; j < n; j++) {
      if(board[i][j] === 1) {
        board[i][j] = 0; //여기서 중요한 점은 큐에 섬의 좌표 정보를 푸쉬해주기 전에 반드시 해당 좌표를 순회한 지점으로 체크해야 한다는 것이다(무한 루프 방지)
        queue.push([i, j]);
        answer++;
        while(queue.length) {
          let [x, y] = queue.shift();
          for(let k = 0; k < m; k++) {
            let nx = x + dx[k];
            let ny = y + dy[k];
            if(nx >= 0 && nx < n && ny >= 0 && ny < n && board[nx][ny] === 1) {
              board[nx][ny] = 0;
              queue.push([nx, ny]);
            }
          }
        }
      }
    }
  }

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