[JS] 백준 10021 Watering the Fields

백준 10021 Watering the Fields

풀이

모든 Field를 최소 비용으로 연결하라는 점에서 MST를 떠올렸습니다. MST를 구하는 알고리즘 중 간선 중심인 Kruskal 알고리즘을 사용하여 풀었습니다.

이 문제에서 메모리 초과, 시간 초과를 모두 겪었습니다.

1. 메모리 초과
   PriorityQueue에 모든 간선을 추가하고 그 이후에는 enqueue하는 일이 발생하지 않습니다. 따라서 PriorityQueue를 클래스로 정의하여 사용했던 방식에서 그냥 배열에 간선을 모두 추가한 후, sort()를 한 번 수행하는 방식으로 변경하였습니다. 그 결과 메모리 초과를 막을 수 있었습니다.

2. 시간 초과
   기존에는 PriorityQueue 정석대로 pq라는 배열을 오름차순으로 정렬하여 shift()를 통해 간선을 뽑아 사용하였습니다. 하지만 shift는 pop보다 시간을 더 많이 사용합니다. 따라서 배열을 내림차순으로 정렬하여 pop을 하여 사용하는 방식으로 변경하였습니다.

이러한 개선을 하여 정답을 맞췄습니다.

코드

const fs = require('fs')
const filePath = process.platform === 'linux' ? 'dev/stdin' : './input.txt'
const input = fs
  .readFileSync(filePath)
  .toString()
  .trim()
  .split('\n')
  .map((el) => el.split(' ').map(Number))

function find(a) {
  if (parent[a] === a) return a
  else return (parent[a] = find(parent[a]))
}

function union(a, b) {
  a = find(a)
  b = find(b)

  if (a === b) return false

  if (a < b) parent[b] = a
  else parent[a] = b

  return true
}

const [N, C] = input.shift()

const pq = []
const parent = Array(N)

for (let i = 0; i < N; i++) parent[i] = i

// 간선 추가
for (let i = 0; i < N - 1; i++) {
  for (let j = i + 1; j < N; j++) {
    const distance =
      Math.pow(Math.abs(input[i][0] - input[j][0]), 2) +
      Math.pow(Math.abs(input[i][1] - input[j][1]), 2)

    if (distance >= C) {
      pq.push({ from: i, to: j, weight: distance })
    }
  }
}

pq.sort((a, b) => b.weight - a.weight)

let result = 0,
  cnt = 0

while (pq.length > 0) {
  const temp = pq.pop()

  if (union(temp.from, temp.to)) {
    result += temp.weight
    cnt += 1

    if (cnt === N - 1) break
  }
}

if (cnt === N - 1) console.log(result)
else console.log(-1)