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

🚩 섬나라 아일랜드 BFS, DFS 풀이

 

📖 문제 설명 : 0과 1로 이루어진 격자판 정보가 주어진다. 이웃한 1의 집합이 곧 하나의 섬이 된다.

몇 개의 섬으로 이루어져 있는지 구해라. (상하좌우 대각선 이동 가능)

 

💡 모든 격자판을 순회하면서 1일 경우 탐색을 하고, 상하좌우 대각선으로 이동하면서 0으로 값을 변경

하나의 탐색이 끝나면 하나의 섬을 탐색한 것이다.

 

BFS

// 섬나라 아일랜드(BFS)

// 상, 하, 좌, 우, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래
const dx = [-1, 1, 0, 0, -1, -1, 1, 1]
const dy = [0, 0, -1, 1, -1, 1, -1, 1]

function BFS(i, j, arr) {
  let queue = []
  queue.push([i, j])
  arr[i][j] = 0
  while (queue.length) {
    let [x, y] = queue.shift()
    for (let k = 0; k < dx.length; k++) {
      let checkX = x + dx[k]
      let checkY = y + dy[k]
      if (checkLength(checkX, checkY, arr.length) && arr[checkX][checkY]) {
        queue.push([checkX, checkY])
        arr[checkX][checkY] = 0
      }
    }
  }
}

// 배열의 인덱스 범위 체크 함수
function checkLength(checkX, checkY, n) {
  if (checkX >= 0 && checkY >= 0 && checkX < n && checkY < n) return true
  else return false
}

function solution(n, arr) {
  let answer = 0

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

  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(7, arr))

 

DFS

// 섬나라 아일랜드(DFS)

// 상, 하, 좌, 우, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래
const dx = [-1, 1, 0, 0, -1, -1, 1, 1]
const dy = [0, 0, -1, 1, -1, 1, -1, 1]

function DFS(arr, x, y) {
  arr[x][y] = 0 // 방문 처리

  for (let i = 0; i < dx.length; i++) {
    let checkX = x + dx[i]
    let checkY = y + dy[i]

    // 유효한 배열 범위 & 방문 하지 않았을 경우
    if (checkLength(checkX, checkY, arr.length) && arr[checkX][checkY]) {
      DFS(arr, checkX, checkY)
    }
  }
}

// 배열의 인덱스 범위 체크 함수
function checkLength(checkX, checkY, n) {
  if (checkX >= 0 && checkY >= 0 && checkX < n && checkY < n) return true
  else return false
}

function solution(n, arr) {
  let answer = 0

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      // 방문하지 않은 경우 탐색 완료 후, 섬 개수 카운트
      if (arr[i][j]) {
        DFS(arr, i, j)
        answer += 1
      }
    }
  }

  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(7, arr))

 

👨‍💻 코드 설명

1. 모든 격자판을 순회하면서 1인 경우 BFS/DFS를 수행한다.

 

2. 상하좌우 대각선이 유효하고 1인 경우 재귀적으로 탐색을 진행하면서 0으로 값을 바꾼다.

 

3. 하나의 BFS/DFS 탐색이 종료되었으면 하나의 섬을 탐색 완료한 것이므로 섬의 개수를 카운트해준다.

 

잘못된 설명, 코드, 예외 케이스가 있다면 댓글 남겨주시면 수정하겠습니다.