[구름톤 챌린지] 연합
노드 사이에 사이클이 발생하면 "연합"이 된다. 각 사이클의 노드가 인접하면 인접한 사이클끼리도 연합이 된다. 이 연합 집합의 개수를 출력하는 문제이다.
이 문제는 그래프에서 사이클을 찾고 집합의 구성을 분류하는 기초적인 문제라 개념 잡기에 좋은 문제인듯 하다.
접근법
사이클을 찾고 해당 사이클이 집합을 이루는지 찾아야 한다. 이 문제는 BFS 또는 Union-Find로 풀릴 수 있다.
먼저 각 노드가 사이클을 가지고 있는지는 어떻게 확인할까? 무지성 includes를 해도 되지만 O(1)로 찾지 않으면 시간초과가 발생한다.
// 그래프의 방향성을 저장하기 위한 2차원 배열을 생성한다.
const check = Array.from(Array(n + 1), () => Array(n + 1).fill(0));
// cur 노드에서 next 노드로 방향성을 가지고 있다면 체크해 준다.
check[cur][next] = 1;
// 현재 노드와 다음 노드의 방향성이 둘 다 1이라면 사이클이다.
check[cur][next] === 1 && check[next][cur] === 1;문제가 친절하게도 각 정점 사이의 직접 사이클만 요구하므로 사이클을 더 쉽게 찾을 수 있다.
각 노드의 사이클 여부를 확인할 수 있게 되었으니 집합을 구성해 주어야 한다.
BFS로 집합 구성하기
인접한 노드끼리 사이클이면서 사이클끼리 인접하면 연합이 된다.
따라서 우리는 각 노드를 순회하면서 사이클을 찾고 사이클이 되는 노드에서 다시 사이클을 찾는 식으로 BFS 탐색을 하면 된다.
const bfs = (i) => {
const q = [i];
memo[i] = 1;
while (q.length) {
// 현재 노드에서 사이클을 찾아간다.
const cur = q.shift();
if (!map[cur]) break; // 현재 노드에서 이어진 노드가 없다면 루프를 탈출한다.
const nextList = map[cur];
for (const next of nextList) {
// 다음 노드가 현재 노드로 사이클이 없거나 방문한 적이 있으면 패스한다.
if (!check[next][cur] || memo[next]) continue;
// 다음 노드와 사이클이면서 방문한 적이 없기 때문에 큐에 넣어준다.
memo[next] = 1;
q.push(next);
}
}
};
let answer = 0;
for (let i = 1; i <= n; i++) {
if (memo[i]) continue;
bfs(i);
// BFS에서 탈출했다면 연합 한 개가 구성된 것이므로 카운트를 추가한다.
answer++;
}
console.log(answer);따라서 각 노드에서 사이클이 되는 노드를 찾고 해당 노드를 큐에 넣어줌으로써 연속된 사이클을 계속해서 찾을 수 있다.
Union-Find로 집합 구성하기
그래프의 집합을 나타내는 방법으로 Union-Find를 사용할 수 있다.
// index 0 1 2 3 4 5 6 7
const parent = [0, 1, 1, 1, 4, 5, 4, 4];
// 1,2,3 인덱스 노드는 부모 노드가 1인 집합이 된다.
// 4,6,7 인덱스 노드는 부모 노드가 4인 집합이 된다.
// 0,5 인덱스 노드는 자기 자신만 집합인 노드가 된다.
for (let cur = 1; cur <= n; cur++) {
const curList = map[cur];
for (const next of curList || []) {
// next -> cur로 이어져 있지 않다는 것은 사이클이 아니므로 무시한다.
if (!check[next][cur]) continue;
// 현재 노드와 다음 노드가 사이클이라면 집합을 구한다.
union(parent, cur, next);
}
}노드를 순회하면서 Union 조건이 성립(사이클)한다면 각 노드를 합쳐준다.
이후 각 노드의 부모 노드를 find 한다. 노드의 부모가 같다면 같은 집합이라는 뜻이 된다.
Union-Find에서는 memo 배열을 통한 방문 여부 확인 코드가 없는 것을 알 수 있다.
- BFS의 경우 인접한 모든 노드를 방문하면서 방문 여부로 집합을 구성하지만, Union-Find는 각 노드의 부모로 집합 여부를 확인하기 때문에 사이클이 된다면 각 노드의 부모를 계속해서 갱신해 줘야 한다.
// 오답
const answer = new Set(parent);
console.log(answer.size);
// 정답
const answer = new Set();
for (let i = 1; i <= n; i++) {
answer.add(find(parent, i));
}
console.log(answer.size);이때 부모 배열의 값으로만 비교해 출력하면 오답이 된다.
모든 노드를 순회하면서 부모를 갱신하지 않았기 때문에 마지막에 각 노드를 다시 find 해서 부모를 갱신해야 올바른 값이 된다.
정리
- 양방향 그래프를 그린다.
- 노드를 순회하면서 사이클 여부를 확인한다.
- 사이클인 노드들을 집합으로 구분한다.
- 집합의 개수를 출력한다.
최종 코드
const readline = require('readline');
let rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
const input = [];
rl.on('line', (line) => {
input.push(line);
});
const l = console.log;
const union = (arr, a, b) => {
const aRoot = find(arr, a);
const bRoot = find(arr, b);
if (aRoot === bRoot) return;
const root = Math.min(aRoot, bRoot);
arr[Math.max(aRoot, bRoot)] = root;
};
const find = (arr, cur) => {
if (arr[cur] === cur) return cur;
// find 하면서 path 단축도 같이한다.
return (arr[cur] = find(arr, arr[cur]));
};
rl.on('close', () => {
const [n, m] = input[0].split(' ').map(Number);
// 부모 노드를 체크할 배열을 index의 값을 가지도록 세팅한다.
const ufArr = Array(n + 1)
.fill(0)
.map((_, idx) => idx);
const check = Array.from(Array(n + 1), () => Array(n + 1).fill(0));
const map = {};
input.slice(1).forEach((line) => {
const [s, e] = line.split(' ').map(Number);
map[s] = [...(map[s] || []), e];
check[s][e] = 1; // 해당 노드의 방향성을 체크한다
});
for (let cur = 1; cur <= n; cur++) {
const curList = map[cur];
for (const next of curList || []) {
// next -> cur로 이어져 있지 않다는 것은 사이클이 아니므로 무시한다.
if (!check[next][cur]) continue;
// 현재 노드와 다음 노드가 사이클이라면 집합을 구한다.
union(ufArr, cur, next);
}
}
const answer = new Set();
for (let i = 1; i <= n; i++) {
// 각 정점의 부모를 find로 순회하며 찾는다.
// Set이므로 중첩된 부모는 제외하고 추가된다.
answer.add(find(ufArr, i));
}
// Set의 size는 중복되지 않는 각 노드의 부모(집합)이므로
// 연합(집합)의 개수가 된다.
console.log(answer.size);
});