[구름톤 챌린지] 연합

1ilsang
1ilsang
클라이밍 하실래염?
published

cover

문제 링크

노드 사이에 사이클이 발생하면 "연합"이 된다. 각 사이클의 노드가 인접하면 인접한 사이클끼리도 연합이 된다. 이 연합 집합의 개수를 출력하는 문제이다.

이 문제는 그래프에서 사이클을 찾고 집합의 구성을 분류하는 기초적인 문제라 개념 잡기에 좋은 문제인듯 하다.

접근법

사이클을 찾고 해당 사이클이 집합을 이루는지 찾아야 한다. 이 문제는 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 해서 부모를 갱신해야 올바른 값이 된다.

정리

  1. 양방향 그래프를 그린다.
  2. 노드를 순회하면서 사이클 여부를 확인한다.
  3. 사이클인 노드들을 집합으로 구분한다.
  4. 집합의 개수를 출력한다.

최종 코드

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);
});