[프로그래머스] [PCCP 기출문제] 2번/ 석유시추 문제풀이 JS

BFS를 활용한 문제이다.

시추관이 뽑을 수 있는 석유의 최대값을 구하기 위해, 

시추관이 들어갈 수 있는 모든 경우의 수를 탐색한다.

 

효율성을 위해 한번 탐색했던 석유 덩어리의 크기는 별도로 저장한다.

(total)

 

시추관이 들어갈 수 있는 모든 경우의 수를 탐색할 때,

해당 위치의 land값이 1이라면 처음 만난 석유 덩어리이므로

Queue를 활용한 BFS탐색을 통해 해당 석유 덩어리의 크기를 구한다.

(상하좌우 가능한 모든 경우의 수를 탐색)

 

다시 재탐색을 막기 위해 해당 값은 visited 표시를 하는데, 

visited는 음수 값으로, 같은 덩어리일 경우 같은 수를 갖게하여

시추관이 같은 석유 덩어리를 뽑는 것인지 판별할 수 있게 구현하였다.

(land에 음수로 업데이트)

 

시추관이 한번 접근된 경우라면, 이미 해당 시추관이 이 석유덩어리에 접근했느지 판별하고,

(!check.includes(land[i][j])

석유 양을 더해준다.

class Queue {
  constructor() {
    this.data = {}
    this.head = 0
    this.tail = 0
  }

  size() {
    return this.tail - this.head
  }

  push(element) {
    this.data[this.tail++] = element
  }

  pop() {
    const removed = this.data[this.head]
    delete this.data[this.head]
    this.head++

    if (this.head === this.tail) {
      this.head = 0
      this.tail = 0
    }
    return removed
  }
}

const solution = (land) => {
  const n = land.length
  const m = land[0].length
  let visited = -1
  const total = {}
  let answer = 0
  const q = new Queue()
  const directions = [
    [1, 0],
    [0, 1],
    [0, -1],
    [-1, 0],
  ]

  for (let j = 0; j < m; j++) {
    let sum = 0
    const check = []
    for (let i = 0; i < n; i++) {
      if (land[i][j] === 1) {
        let count = 1
        land[i][j] = visited
        q.push([i, j])
        while (q.size() !== 0) {
          const [x, y] = q.pop()
          for (const [dx, dy] of directions) {
            const nx = x + dx
            const ny = y + dy
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && land[nx][ny] === 1) {
              count++
              land[nx][ny] = visited
              q.push([nx, ny])
            }
          }
        }
        sum += count
        check.push(visited)
        total[visited--] = count
      } else if (land[i][j] < 0 && !check.includes(land[i][j])) {
        check.push(land[i][j])
        sum += total[land[i][j]]
      }
    }
    if (sum > answer) answer = sum
  }
  return answer
}

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/250136