[Javascript로 정리하는 이코테] 9. 그래프 이론

http://www.yes24.com/Product/Goods/91433923

이것이 취업을 위한 코딩 테스트다 with 파이썬 - YES24

 

 

💡 서로 다른 개체가 연결되어 있다는 이야기를 들으면 가장 먼저 그래프 알고리즘을 떠올리자.

 

서로소 집합

• 서로소 집합이란 공통 원소가 없는 두 집합을 의미한다.
• 서로소 집합 자료구조란 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조이다.
• 서로소 집합 자료구조는 합집합(union)과 찾기(find) 연산으로 구성된다.
  • 그래서 union-find 자료구조라고 불린다.

 

구현

• 트리를 이용해 집합을 표현한다.
• 서로소 집합 계산(표현) 알고리즘
  1. union 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인한다.
     1. A와 B의 루트 노드 A’, B’를 각각 찾는다.
     2. A’를 B’의 부모 노드로 설정한다. (A’ < B’인 경우를 따름)
  2. 모든 union 연산을 처리할 때까지 1번 과정을 반복한다.

 

이렇게 union연산을 토대로 그래프를 그리면 ‘연결성’으로 쉽게 집합의 형태를 확인할 수 있다. 특정 원소들이 같은 집합에 포함되어 있는지 여부를 파악할 수 있다.

 

 

예제 10-1. 기본적인 서로소 집합 알고리즘

const fs = require('fs');
let input = fs.readFileSync('../tc.txt').toString().trim().split('\n');

let [nm, ...arr] = input;
const [n, m] = nm.split(' ').map((v) => +v);
const edges = arr.map((str) => str.split(' ').map((v) => +v));

//특정 원소가 속한 집합 찾기 (루트 찾기)
const findParent = (parent, x) => {
  if (parent[x] === x) return x;
  return findParent(parent, parent[x]);
};

//두 원소가 속한 집합을 합치기 (루트 갱신)
const unionParent = (parent, a, b) => {
  a = findParent(parent, a);
  b = findParent(parent, b);
  if (a < b) parent[b] = a;
  else parent[a] = b;
};

function solution(n, m, edges) {
  //부모 테이블 초기화
  let parent = [...Array(n + 1).fill(0)];
  for (let i = 1; i <= n; i++) {
    parent[i] = i;
  }

  //union 연산 수행
  for (const edge of edges) {
    const [a, b] = edge;
    unionParent(parent, a, b);
  }

  //각 원소가 속한 집합 출력
  let sets = '';
  for (let i = 1; i <= n; i++) {
    sets += findParent(parent, i);
  }

  console.log(`각 원소가 속한 집합: ${sets.split('').join(' ')}`);
  console.log(`부모 테이블: ${parent.slice(1, n).join(' ')}`);
}

solution(n, m, edges);

 

예제 10-2. 경로 압축 기법

• 위 코드의 findParent 함수는 최악의 경우 O(n)의 시간복잡도를 가진다.
• 경로 압축 기법을 적용하면 이 부분을 최적화할 수 있다.
  • 경로 압축은 findParent 함수를 재귀적으로 호출한 뒤에 부모 테이블 값을 갱신하는 기법이다.
  • 해당 노드의 부모 테이블의 값이 루트 노드를 가리키도록 하는 것이다.

const findParent = (parent, x) => {
  if (parent[x] === x) return parent[x];
  return (parent[x] = findParent(parent, parent[x]));
};

 

예제 10-3. 개선된 서로소 집합 알고리즘

• union 및 find 연산이 총 100만(10^7) 번 수행된다고 할 때, 대략 1,000만(10^8) 번의 연산이 필요하다고 볼 수 있다. (시간복잡도가 복잡하니 이렇게만 이해하자)

//특정 원소가 속한 집합 찾기 (루트 찾기)
const findParent = (parent, x) => {
  if (parent[x] === x) return parent[x];
  return (parent[x] = findParent(parent, parent[x]));
};

//두 원소가 속한 집합을 합치기 (루트 갱신)
const unionParent = (parent, a, b) => {
  a = findParent(parent, a);
  b = findParent(parent, b);
  if (a < b) parent[b] = a;
  else parent[a] = b;
};

function solution(n, m, edges) {
  //부모 테이블 초기화
  let parent = [...Array(n + 1).fill(0)];
  for (let i = 1; i <= n; i++) {
    parent[i] = i;
  }

  //union 연산 수행
  for (const edge of edges) {
    const [a, b] = edge;
    unionParent(parent, a, b);
  }

  //각 원소가 속한 집합 출력
  let sets = '';
  for (let i = 1; i <= n; i++) {
    sets += findParent(parent, i);
  }

  console.log(`각 원소가 속한 집합: ${sets.split('').join(' ')}`);
  console.log(`부모 테이블: ${parent.slice(1, n).join(' ')}`);
}

solution(n, m, edges);

 

서로소 집합을 활용한 사이클 판별

• 서로소 집합은 무방향 그래프 내에서 사이클을 판별할 때 사용할 수 있다는 특징이 있다.
  • 참고로 방향 그래프에서의 사이클 여부는 DFS를 활용하면 된다.
• 사이클 판별 알고리즘 동작 과정
  1. 각 간선을 확인하며 두 노드의 루트 노드를 확인 (소속 확인)
     1. 루트 노드가 서로 다르다면 → 두 노드에 대하여 union 연산을 수행
     2. 루트 노드가 서로 같다면 → 사이클 발생
  2. 그래프에 포함되어 있는 모든 간선에 대하여 1번 과정을 반복
• 간선 정보를 확인하는 시점에 두 노드가 이미 같은 집합에 속해 있다면, 현재 그래프에 사이클이 존재한다고 볼 수 있다.

 

예제 10-4. 서로소 집합을 활용한 사이클 판별

function solution(n, m, edges) {
  let parent = [...Array(n + 1).fill(0)];
  for (let i = 1; i <= n; i++) {
    parent[i] = i;
  }

  let isCycle = false;
  for (const edge of edges) {
    const [a, b] = edge;
    if (parent[a] !== parent[b]) unionParent(parent, a, b);
    else {
      isCycle = true;
      break;
    }
  }

  console.log(
    isCycle ? '사이클이 발생했습니다.' : '사이클이 발생하지 않았습니다.'
  );
}

solution(n, m, edges);

 

 

크루스칼 알고리즘

• 크루스칼 알고리즘은 대표적인 최소 신장 트리 알고리즘이다.
• 신장 트리란 하나의 그래프가 있을 때, 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다.
• 최소 신장 트리 알고리즘이란 신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘이다.
• 시간복잡도: O(nlogn)

 

동작 과정

1. 간선 데이터를 비용에 따라 오름차순으로 정렬
2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인
   1. 사이클이 발생하지 않는 경우 → 최소 신장 트리에 포함 O
   2. 사이클이 발생하는 경우 → 최소 신장 트리에 포함 X
3. 모든 간선에 대하여 2번 과정을 반복

 

크루스칼 알고리즘은 가장 거리가 짧은 간선부터 사이클을 발생시키는 간선을 제외하고 차례대로 집합에 추가한다는 점에서 그리디 알고리즘의 유형으로 볼 수 있다.

 

 

예제 10-5. 크루스칼 알고리즘

const fs = require('fs');
let input = fs.readFileSync('../tc.txt').toString().trim().split('\n');

let [nm, ...arr] = input;
const [n, m] = nm.split(' ').map((v) => +v);
arr = arr.map((str) => str.split(' ').map((v) => +v));

const findParent = (parent, x) => {
  if (parent[x] === x) return parent[x];
  return (parent[x] = findParent(parent, parent[x]));
};

const unionParent = (parent, a, b) => {
  a = findParent(parent, a);
  b = findParent(parent, b);
  if (a < b) parent[b] = a;
  else parent[a] = b;
};

function solution(n, m, arr) {
  let parent = [...Array(n + 1).fill(0)];
  for (let i = 1; i <= n; i++) {
    parent[i] = i;
  }

  let edges = [];
  for (const value of arr) {
    const [u, v, cost] = value;
    edges.push([cost, u, v]);
  }

	//오름차순 정렬
  edges.sort((a, b) => a[0] - b[0]);

  let result = 0;

	//모든 간선 확인
  for (const edge of edges) {
    const [cost, a, b] = edge;
		//사이클이 발생하지 않는 경우에만 집합에 포함
    if (findParent(parent, a) !== findParent(parent, b)) {
      unionParent(parent, a, b);
      result += cost;
    }
  }

  return result;
}

console.log(solution(n, m, arr));

 

 

위상 정렬

• 위상 정렬은 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘
• 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것이다.
• 시간복잡도: O(n+m)

 

동작 과정

1. 진입 차수가 0인 노드를 큐에 삽입
2. 큐가 빌 때까지 다음 과정을 반복
   1. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거
   2. 새롭게 진입차수가 0이 된 노드를 큐에 삽입

 

이때 모든 원소를 방문하기 전에 큐가 빈다면, 사이클이 존재한다고 볼 수 있다.

 

 

예제 10-6. 위상 정렬

const fs = require('fs');
let input = fs.readFileSync('../tc.txt').toString().trim().split('\n');

let [nm, ...arr] = input;
const [n, m] = nm.split(' ').map((v) => +v);
arr = arr.map((str) => str.split(' ').map((v) => +v));

let indegree = [...Array(n + 1).fill(0)];
function solution(n, m, arr) {
  let graph = Array.from(Array(n + 1), () => []);

	//그래프 및 진입 차수 초기화
  for (const value of arr) {
    const [u, v] = value;
    graph[u].push(v);
    indegree[v]++;
  }

  const q = new Queue();
  for (let i = 1; i <= n; i++) {
		//진입 차수가 0인 노드 큐에 삽입
    if (indegree[i] === 0) q.enqueue(i);
  }

  let sorted = [];
  while (!q.empty()) {
    const cur = q.dequeue();
    sorted.push(cur);

    for (const node of graph[cur]) {
      indegree[node]--; //간선 제거
      if (indegree[node] === 0) q.enqueue(node); //진입 차수가 0이 된 노드 큐에 삽입
    }
  }

  return sorted;
}

console.log(solution(n, m, arr));

 

 

실전 문제

팀 결성

• 유니온 파인드 알고리즘

const fs = require('fs');
let input = fs.readFileSync('../tc.txt').toString().trim().split('\n');

let [n, ...arr] = input;
n = +n;
arr = arr.map((str) => str.split(' ').map((v) => +v));

function solution(n, arr) {
  let indegree = [...Array(n + 1).fill(0)];
  let graph = Array.from(Array(n + 1), () => []);
  let times = [...Array(n + 1).fill(0)];

  for (let i = 0; i < arr.length; i++) {
    const [time, ...rest] = arr[i];
    for (let j = 0; j < rest.length - 1; j++) {
      graph[rest[j]].push(i + 1);
    }
    indegree[i + 1] = rest.length - 1;
    times[i + 1] = time;
  }

  let result = [];

  const q = new Queue();
  for (let i = 1; i <= n; i++) {
    if (indegree[i] === 0) {
      q.enqueue(i);
      result[i] = times[i];
    }
  }

  while (!q.isEmpty()) {
    const cur = q.dequeue();
    for (const node of graph[cur]) {
      result[node] = result[cur] + times[node];

      indegree[node]--;
      if (indegree[node] === 0) q.enqueue(node);
    }
  }

  for (let i = 1; i <= n; i++) {
    console.log(result[i]);
  }
}

solution(n, arr);

 

도시 분할 계획

• 크루스칼 알고리즘
• 가장 마지막에 추가되는 도시는 제외

const fs = require('fs');
let input = fs.readFileSync('../tc.txt').toString().trim().split('\n');

let [nm, ...arr] = input;
const [n, m] = nm.split(' ').map((v) => +v);
arr = arr.map((str) => str.split(' ').map((v) => +v));

function solution(n, m, arr) {
  const findParent = (parent, x) => {
    if (parent[x] === x) return parent[x];
    else return (parent[x] = findParent(parent, parent[x]));
  };

  const unionParent = (parent, a, b) => {
    a = findParent(parent, a);
    b = findParent(parent, b);
    if (a < b) parent[b] = a;
    else parent[a] = b;
  };

  let parent = [...Array(n + 1).fill(0)];
  for (let i = 1; i <= n; i++) {
    parent[i] = i;
  }

  let edges = [];
  for (const value of arr) {
    const [u, v, cost] = value;
    edges.push([cost, u, v]);
  }

  edges.sort((a, b) => a[0] - b[0]);

  let total = 0;
  let last = 0;
  for (const edge of edges) {
    const [cost, u, v] = edge;
    if (findParent(parent, u) !== findParent(parent, v)) {
      unionParent(parent, u, v);
      total += cost;
      last = cost;
    }
  }

  return total - last;
}

console.log(solution(n, m, arr));

 

커리큘럼

• 위상 정렬 알고리즘
• 인접 노드 탐색할 때, 강의를 수강하기까지 걸리는 시간 갱신

const fs = require('fs');
let input = fs.readFileSync('../tc.txt').toString().trim().split('\n');

let [n, ...arr] = input;
n = +n;
arr = arr.map((str) => str.split(' ').map((v) => +v));

function solution(n, arr) {
  let indegree = [...Array(n + 1).fill(0)];
  let graph = Array.from(Array(n + 1), () => []);
  let times = [...Array(n + 1).fill(0)];

  for (let i = 0; i < arr.length; i++) {
    const [time, ...rest] = arr[i];
    for (let j = 0; j < rest.length - 1; j++) {
      graph[rest[j]].push(i + 1);
    }
    indegree[i + 1] = rest.length - 1;
    times[i + 1] = time;
  }

  let result = [];

  const q = new Queue();
  for (let i = 1; i <= n; i++) {
    if (indegree[i] === 0) {
      q.enqueue(i);
      result[i] = times[i];
    }
  }

  while (!q.isEmpty()) {
    const cur = q.dequeue();
    for (const node of graph[cur]) {
      result[node] = result[cur] + times[node];

      indegree[node]--;
      if (indegree[node] === 0) q.enqueue(node);
    }
  }

  for (let i = 1; i <= n; i++) {
    console.log(result[i]);
  }
}

solution(n, arr);