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

문제 번호

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

 

 

알고리즘 분류

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

 

문제 풀이

 처음 풀어보는 Union-Find 알고리즘 문제이다. 

아래의 블로그의 설명을 참고하여 문제를 풀었다.

17. Union-Find(합집합 찾기)

 

 유니온 파인드는 서로 중복되지 않는 부분 집합들을 찾아내는 알고리즘이다.

대략적으로 make-set, union(x,y), find(x) 의 연산을 갖는다.

make-set을 통하여 초기화를 시켜준다.

union은 두개의 부분집합을 하나로 합칠 때 사용하고 find는 해당 원소를 갖는 부분집합의 root를 찾을 때 사용한다.

 

유니온 파인드 알고리즘의 내용을 알고 있다면 문제는 간단하게 풀 수 있다. 그러나 이번에도 Node.js 로는 시간초과에 걸렸다. 그래서 같은 로직을 사용한 C++ 코드를 제출하였다.

 

 node.js 로 문제를 풀때 shift를 사용해서 변수를 받아왔었었는데 그것때문에 시간초과에 걸리는 일이 많았다.

해당 내용이 기억이나서 수정해주니까 통과하였다.

 

전체코드 JS

// 노드의 부모를 확인한다.
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() {
  const fs = require('fs').readFileSync('dev/stdin').toString().trim().split('\n');
  const N = +fs[0];

  // make-set
  let parent = [0];
  for(let i=1; i<=N; i++){
    parent[i] = i;
  }
  
  // 문제에서 주어진 다리들을 연결시킨다.
  for (let i = 0; i < N - 2; i++) {
    let startEnd = fs[i+1].split(' ').map(_ => Number(_));
    start = startEnd[0];
    end = startEnd[1];
    unionParent(parent, start, end);
  }
  for(let i=1; i<=N; i++){
    if(findParent(parent,1,i) === 1)
      continue;
    else if(findParent(parent,1,i) === 0){
      console.log(getParent(parent,1), getParent(parent,i));
      unionParent(parent,1,i);
    }
  }
  
}

main();

 

전체코드 C++

#include<iostream>
using namespace std;

int getParent(int* parent, int x) {
	if (parent[x] == x)	return x;
	return parent[x] = getParent(parent, parent[x]);
}

void unionParent(int* parent, int a, int b) {
	a = getParent(parent, a);
	b = getParent(parent, b);
	if (a < b) parent[b] = a;
	else parent[a] = b;
}

int findParent(int* parent, int a, int b) {
	a = getParent(parent, a);
	b = getParent(parent, b);
	if (a == b)	return 1;
	else return 0;
}

int main() {
	int N; cin >> N;
	int* parent = new int[N+1];

	//make-set
	for (int i = 1; i <= N; i++) {
		parent[i] = i;
	}
	// init graph
	for (int i = 0; i < N - 2; i++) {
		int start; cin >> start;
		int end; cin >> end;
		unionParent(parent, start, end);
	}
	for (int i = 1; i <= N; i++) {
		if (findParent(parent, 1, i) == 1)
			continue;
		else if (findParent(parent, 1, i) == 0) {
			cout << getParent(parent, 1) << ' ' << getParent(parent, i) << endl;
			unionParent(parent, 1, i);
		}
	}
	//system("pause");
}

특이사항