[JS][백준]17352_여러분의 다리가 되어 드리겠습니다!

문제 번호

17352번: 여러분의 다리가 되어 드리겠습니다!

 

 

 

알고리즘 분류

• 그래프 이론
• 자료 구조
• 그래프 탐색
• 분리 집합

 

문제 풀이

 Union-Find(합집합 찾기)를 사용하여 문제를 풀었다.

문제에서 모든 마을이 이어져있었는데 1개의 다리를 파괴하였다고 하였으니 문제에서 주어진 섬들은 총 2개의 덩어리로 나뉘어 있을 것이다. 그렇기 때문에 유니온 파인드를 사용해서 각각의 섬이 갖는 부모 노드를 찾고 다른 부모 노드를 갖는 섬이 발견됐을 때 이 섬들을 이어주면 문제를 해결할 수 있다.

 

전체 코드

const input = require('fs').readFileSync('input.txt').toString().trim().split('\n');
const N = +input[0];

function getParent(parent, x) {  // 부모노드 구하기.
  if (parent[x] === x) return x;
  return parent[x] = getParent(parent, parent[x]);
}
function unionParent(parent, a, b) {  // 합집합 만들기.
  a = getParent(parent, a);
  b = getParent(parent, b);
  if (a < b) parent[b] = a;
  else parent[a] = b;
}
function findParent(parent, a, b) {  // 같은 부모노드를 갖는지 확인하기.
  a = getParent(parent, a);
  b = getParent(parent, b);
  if (a === b) return 1;
  else return 0;
}
function main() {
  let parent = new Array(N + 1).fill(0).map(function (e, i) {
    return i;
  })
  for (let i = 1; i < input.length; i++) {
    let [a, b] = input[i].split(' ').map(Number);
    unionParent(parent, a, b)
  }
  for (let i = 2; i <= N; i++) {
    if (!findParent(parent, 1, i)) {
      return console.log(1, i)
    }
  }
}
main()

특이사항