[JS][백준]1647_도시 분할 계획

문제 번호

1647번: 도시 분할 계획

 

 

알고리즘 분류

• 그래프 이론
• 최소 스패닝 트리

 

문제 풀이

 최소 스패닝 트리(MST)를 이용하는 문제이다. MST를 사용하기 위해서는 Union-Find 알고리즘을 알아야 한다. 왜냐하면 MST를 만들 때 MST에 사이클(cycle)이 존재하는지 확인해야 하는데 이때 Union-Find 알고리즘이 사용되기 때문이다.

 

Union-Find 알고리즘 코드.

function getParent(x, parent) {
  if (parent[x] === x) return x;
  else return parent[x] = getParent(parent[x], parent); // return 이 있어야 축약됨.
}
function findParent(a, b, parent) {
  a = getParent(a,parent);
  b = getParent(b,parent);
  if (a === b) return true;
  else return false;
}
function unionParent(a, b, parent) {
  a = parent[a];
  b = parent[b];
  if (a < b) parent[b] = a;
  else parent[a] = b;
}

 

 문제에서 처음 주어지는 정보에는 모든 집들이 연결되어 있다고 하였다. 그렇기 때문에 입력받은 집들 사이의 정보를 vilage라는 배열에 추가해주고, 유지비를 기준으로 오름차순으로 정렬해준다.

let village = [];
  for (let i = 0; i < road.length; i++) {
    let [A, B, C] = road[i];  // A -> B : C.
    village.push({
      from: A,
      to: B,
      cost: C
    })
  }
  village.sort((a, b) => {
    a = a.cost;
    b = b.cost;
    if (a > b) return 1;
    else if (a < b) return -1;
  })

 

 이제 village 배열을 탐색하면서 MST를 작성해주면 된다. 간선의 비용이 낮은 순서부터 확인하면서 MST에 싸이클을 생성하지 않는 정점이라면 MST에 추가한다.

let MST = [];
  //console.log(village)
  for (let i = 0; i < village.length; i++) {
    let [a, b, c] = [village[i].to, village[i].from, village[i].cost];
    // cycle check.
    if (!findParent(a, b, parent)) {
      unionParent(a, b, parent);
      MST.push({
        from: a,
        to: b,
        cost: c
      })
    } 
  }

 

 MST가 완성되었다면 MST를 이루는 간선중에서 비용이 가장 큰 간선을 제거하고 남은 간선들의 비용을 모두 더해준다.

// 비용이 젤 높은 간선 자르기.
  MST.pop()
  for(let i=0; i<MST.length; i++) {
    sum += MST[i].cost;
  }

 

전체 코드

/**
MST를 만든다.
MSt중 가장 비용이 큰 간선을 자른다.
남은 간선들의 합을 구한다. 
 */

function main() {
  let answer = 0;
  const input = require('fs').readFileSync('input.txt').toString().trim().split('\n');
  const [N, M] = input[0].split(' ').map(Number);
  let road = input.slice(1).map(_ => _.trim().split(' ').map(Number));

  let village = [];
  for (let i = 0; i < road.length; i++) {
    let [A, B, C] = road[i];  // A -> B : C.
    village.push({
      from: A,
      to: B,
      cost: C
    })
  }
  village.sort((a, b) => {
    a = a.cost;
    b = b.cost;
    if (a > b) return 1;
    else if (a < b) return -1;
  })
  //console.log(village)

  // unionFind
  let parent = new Array(N + 1).fill(0);
  for (let i = 0; i <= N; i++) {
    parent[i] = i;
  }

  answer = sol(village,parent);

  return console.log(answer)
}
function sol(village, parent) {
  let sum = 0;

  let MST = [];
  //console.log(village)
  for (let i = 0; i < village.length; i++) {
    let [a, b, c] = [village[i].to, village[i].from, village[i].cost];
    // cycle check.
    if (!findParent(a, b, parent)) {
      unionParent(a, b, parent);
      MST.push({
        from: a,
        to: b,
        cost: c
      })
    } 
  }
  // 비용이 젤 높은 간선 자르기.
  MST.pop()
  for(let i=0; i<MST.length; i++) {
    sum += MST[i].cost;
  }

  return sum;
}
function getParent(x, parent) {
  if (parent[x] === x) return x;
  else return parent[x] = getParent(parent[x], parent); // return 이 있어야 축약됨.
}
function findParent(a, b, parent) {
  a = getParent(a,parent);
  b = getParent(b,parent);
  if (a === b) return true;
  else return false;
}
function unionParent(a, b, parent) {
  a = parent[a];
  b = parent[b];
  if (a < b) parent[b] = a;
  else parent[a] = b;
}
main();

 

특이사항

Union-Find 알고리즘을 사용할때 getParent 함수에서 parent[x] = x 가 아닐 때 return을 빼먹지 말자.

return을 빼먹으면 경로 압축이 이루어지지 않는다.