[코딩 테스트] 17일차: 그래프의 심화 알고리즘

그래프의 심화 알고리즘

이번 글에서는 그래프의 심화 알고리즘에 대해 알아보겠습니다. 위상 정렬, 강결합 컴포넌트, 최소 컷 최대 유량 등의 알고리즘을 살펴보겠습니다.

위상 정렬 (Topological Sort)

위상 정렬은 방향 그래프의 모든 노드를 순서대로 나열하는 알고리즘입니다. 주로 작업의 순서를 결정할 때 사용됩니다. 위상 정렬은 사이클이 없는 방향 그래프(DAG)에서만 적용 가능합니다.

 

예제: 위상 정렬 구현 (Kahn's Algorithm)

JavaScript

function topologicalSort(vertices, edges) {
  const adjList = new Map();
  const inDegree = new Map();
  const queue = [];
  const result = [];

  vertices.forEach(v => {
    adjList.set(v, []);
    inDegree.set(v, 0);
  });

  edges.forEach(([u, v]) => {
    adjList.get(u).push(v);
    inDegree.set(v, inDegree.get(v) + 1);
  });

  inDegree.forEach((degree, v) => {
    if (degree === 0) {
      queue.push(v);
    }
  });

  while (queue.length > 0) {
    const u = queue.shift();
    result.push(u);

    adjList.get(u).forEach(v => {
      inDegree.set(v, inDegree.get(v) - 1);
      if (inDegree.get(v) === 0) {
        queue.push(v);
      }
    });
  }

  return result.length === vertices.length ? result : [];
}

const vertices = [0, 1, 2, 3, 4, 5];
const edges = [
  [5, 2],
  [5, 0],
  [4, 0],
  [4, 1],
  [2, 3],
  [3, 1]
];

console.log(topologicalSort(vertices, edges)); // [5, 4, 2, 3, 1, 0]

Python

from collections import defaultdict, deque

def topological_sort(vertices, edges):
    adj_list = defaultdict(list)
    in_degree = {v: 0 for v in vertices}
    queue = deque()
    result = []

    for u, v in edges:
        adj_list[u].append(v)
        in_degree[v] += 1

    for v in in_degree:
        if in_degree[v] == 0:
            queue.append(v)

    while queue:
        u = queue.popleft()
        result.append(u)

        for v in adj_list[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)

    return result if len(result) == len(vertices) else []

vertices = [0, 1, 2, 3, 4, 5]
edges = [
    (5, 2),
    (5, 0),
    (4, 0),
    (4, 1),
    (2, 3),
    (3, 1)
]

print(topological_sort(vertices, edges)) # [5, 4, 2, 3, 1, 0]

강결합 컴포넌트 (Strongly Connected Components, SCC)

강결합 컴포넌트는 그래프의 모든 정점이 서로 연결된 부분 그래프입니다. Kosaraju's Algorithm은 두 번의 DFS를 이용하여 강결합 컴포넌트를 찾습니다.

 

예제: Kosaraju's Algorithm 구현

JavaScript

function kosaraju(vertices, edges) {
  const adjList = new Map();
  const reverseAdjList = new Map();
  const stack = [];
  const visited = new Set();
  const scc = [];

  vertices.forEach(v => {
    adjList.set(v, []);
    reverseAdjList.set(v, []);
  });

  edges.forEach(([u, v]) => {
    adjList.get(u).push(v);
    reverseAdjList.get(v).push(u);
  });

  function dfs(node, list, visited, result) {
    visited.add(node);
    list.get(node).forEach(neighbor => {
      if (!visited.has(neighbor)) {
        dfs(neighbor, list, visited, result);
      }
    });
    result.push(node);
  }

  vertices.forEach(v => {
    if (!visited.has(v)) {
      dfs(v, adjList, visited, stack);
    }
  });

  visited.clear();

  while (stack.length > 0) {
    const v = stack.pop();
    if (!visited.has(v)) {
      const component = [];
      dfs(v, reverseAdjList, visited, component);
      scc.push(component);
    }
  }

  return scc;
}

const vertices = [0, 1, 2, 3, 4];
const edges = [
  [0, 2],
  [2, 1],
  [1, 0],
  [0, 3],
  [3, 4]
];

console.log(kosaraju(vertices, edges)); // [[4], [3], [0, 1, 2]]

Python

from collections import defaultdict

def kosaraju(vertices, edges):
    adj_list = defaultdict(list)
    reverse_adj_list = defaultdict(list)
    stack = []
    visited = set()
    scc = []

    for u, v in edges:
        adj_list[u].append(v)
        reverse_adj_list[v].append(u)

    def dfs(node, graph, visited, result):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs(neighbor, graph, visited, result)
        result.append(node)

    for v in vertices:
        if v not in visited:
            dfs(v, adj_list, visited, stack)

    visited.clear()

    while stack:
        v = stack.pop()
        if v not in visited:
            component = []
            dfs(v, reverse_adj_list, visited, component)
            scc.append(component)

    return scc

vertices = [0, 1, 2, 3, 4]
edges = [
    (0, 2),
    (2, 1),
    (1, 0),
    (0, 3),
    (3, 4)
]

print(kosaraju(vertices, edges)) # [[4], [3], [0, 1, 2]]

최소 컷 최대 유량 (Min-Cut Max-Flow)

최소 컷 최대 유량 정리는 네트워크 유량 문제에서 최대 유량과 최소 컷이 같음을 나타냅니다. Ford-Fulkerson 알고리즘은 이 문제를 해결하는 대표적인 방법입니다.

 

예제: Ford-Fulkerson 알고리즘 구현

JavaScript

class Graph {
  constructor(size) {
    this.size = size;
    this.graph = Array.from({ length: size }, () => Array(size).fill(0));
  }

  addEdge(u, v, capacity) {
    this.graph[u][v] = capacity;
  }

  bfs(source, sink, parent) {
    const visited = Array(this.size).fill(false);
    const queue = [source];
    visited[source] = true;

    while (queue.length > 0) {
      const u = queue.shift();

      for (let v = 0; v < this.size; v++) {
        if (!visited[v] && this.graph[u][v] > 0) {
          queue.push(v);
          visited[v] = true;
          parent[v] = u;

          if (v === sink) {
            return true;
          }
        }
      }
    }

    return false;
  }

  fordFulkerson(source, sink) {
    const parent = Array(this.size).fill(-1);
    let maxFlow = 0;

    while (this.bfs(source, sink, parent)) {
      let pathFlow = Infinity;
      let s = sink;

      while (s !== source) {
        pathFlow = Math.min(pathFlow, this.graph[parent[s]][s]);
        s = parent[s];
      }

      s = sink;
      while (s !== source) {
        const u = parent[s];
        this.graph[u][s] -= pathFlow;
        this.graph[s][u] += pathFlow;
        s = parent[s];
      }

      maxFlow += pathFlow;
    }

    return maxFlow;
  }
}

const graph = new Graph(6);
graph.addEdge(0, 1, 16);
graph.addEdge(0, 2, 13);
graph.addEdge(1, 2, 10);
graph.addEdge(1, 3, 12);
graph.addEdge(2, 1, 4);
graph.addEdge(2, 4, 14);
graph.addEdge(3, 2, 9);
graph.addEdge(3, 5, 20);
graph.addEdge(4, 3, 7);
graph.addEdge(4, 5, 4);

console.log(graph.fordFulkerson(0,

 5)); // 23

Python

from collections import deque

class Graph:
    def __init__(self, size):
        self.size = size
        self.graph = [[0] * size for _ in range(size)]

    def add_edge(self, u, v, capacity):
        self.graph[u][v] = capacity

    def bfs(self, source, sink, parent):
        visited = [False] * self.size
        queue = deque([source])
        visited[source] = True

        while queue:
            u = queue.popleft()

            for v in range(self.size):
                if not visited[v] and self.graph[u][v] > 0:
                    queue.append(v)
                    visited[v] = True
                    parent[v] = u

                    if v == sink:
                        return True

        return False

    def ford_fulkerson(self, source, sink):
        parent = [-1] * self.size
        max_flow = 0

        while self.bfs(source, sink, parent):
            path_flow = float('Inf')
            s = sink

            while s != source:
                path_flow = min(path_flow, self.graph[parent[s]][s])
                s = parent[s]

            v = sink
            while v != source:
                u = parent[v]
                self.graph[u][v] -= path_flow
                self.graph[v][u] += path_flow
                v = parent[v]

            max_flow += path_flow

        return max_flow

graph = Graph(6)
graph.add_edge(0, 1, 16)
graph.add_edge(0, 2, 13)
graph.add_edge(1, 2, 10)
graph.add_edge(1, 3, 12)
graph.add_edge(2, 1, 4)
graph.add_edge(2, 4, 14)
graph.add_edge(3, 2, 9)
graph.add_edge(3, 5, 20)
graph.add_edge(4, 3, 7)
graph.add_edge(4, 5, 4)

print(graph.ford_fulkerson(0, 5)) # 23

연습 문제

문제 1: 강결합 컴포넌트 찾기

주어진 그래프에서 강결합 컴포넌트를 찾는 프로그램을 작성하세요.

JavaScript

function findSCC(vertices, edges) {
  const adjList = new Map();
  const reverseAdjList = new Map();
  const stack = [];
  const visited = new Set();
  const scc = [];

  vertices.forEach(v => {
    adjList.set(v, []);
    reverseAdjList.set(v, []);
  });

  edges.forEach(([u, v]) => {
    adjList.get(u).push(v);
    reverseAdjList.get(v).push(u);
  });

  function dfs(node, list, visited, result) {
    visited.add(node);
    list.get(node).forEach(neighbor => {
      if (!visited.has(neighbor)) {
        dfs(neighbor, list, visited, result);
      }
    });
    result.push(node);
  }

  vertices.forEach(v => {
    if (!visited.has(v)) {
      dfs(v, adjList, visited, stack);
    }
  });

  visited.clear();

  while (stack.length > 0) {
    const v = stack.pop();
    if (!visited.has(v)) {
      const component = [];
      dfs(v, reverseAdjList, visited, component);
      scc.push(component);
    }
  }

  return scc;
}

const vertices = [0, 1, 2, 3, 4];
const edges = [
  [0, 2],
  [2, 1],
  [1, 0],
  [0, 3],
  [3, 4]
];

console.log(findSCC(vertices, edges)); // [[4], [3], [0, 1, 2]]

Python

from collections import defaultdict

def find_scc(vertices, edges):
    adj_list = defaultdict(list)
    reverse_adj_list = defaultdict(list)
    stack = []
    visited = set()
    scc = []

    for u, v in edges:
        adj_list[u].append(v)
        reverse_adj_list[v].append(u)

    def dfs(node, graph, visited, result):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs(neighbor, graph, visited, result)
        result.append(node)

    for v in vertices:
        if v not in visited:
            dfs(v, adj_list, visited, stack)

    visited.clear()

    while stack:
        v = stack.pop()
        if v not in visited:
            component = []
            dfs(v, reverse_adj_list, visited, component)
            scc.append(component)

    return scc

vertices = [0, 1, 2, 3, 4]
edges = [
    (0, 2),
    (2, 1),
    (1, 0),
    (0, 3),
    (3, 4)
]

print(find_scc(vertices, edges)) # [[4], [3], [0, 1, 2]]

문제 2: 최대 유량 구하기

주어진 네트워크에서 최대 유량을 구하는 프로그램을 작성하세요.

JavaScript

class Graph {
  // ... (이전 Ford-Fulkerson 알고리즘 코드와 동일)

  maxFlow(source, sink) {
    return this.fordFulkerson(source, sink);
  }
}

const graph = new Graph(6);
graph.addEdge(0, 1, 16);
graph.addEdge(0, 2, 13);
graph.addEdge(1, 2, 10);
graph.addEdge(1, 3, 12);
graph.addEdge(2, 1, 4);
graph.addEdge(2, 4, 14);
graph.addEdge(3, 2, 9);
graph.addEdge(3, 5, 20);
graph.addEdge(4, 3, 7);
graph.addEdge(4, 5, 4);

console.log(graph.maxFlow(0, 5)); // 23

Python

class Graph:
    # ... (이전 Ford-Fulkerson 알고리즘 코드와 동일)

    def max_flow(self, source, sink):
        return self.ford_fulkerson(source, sink)

graph = Graph(6)
graph.add_edge(0, 1, 16)
graph.add_edge(0, 2, 13)
graph.add_edge(1, 2, 10)
graph.add_edge(1, 3, 12)
graph.add_edge(2, 1, 4)
graph.add_edge(2, 4, 14)
graph.add_edge(3, 2, 9)
graph.add_edge(3, 5, 20)
graph.add_edge(4, 3, 7)
graph.add_edge(4, 5, 4)

print(graph.max_flow(0, 5)) # 23

결론

이번 글에서는 코딩 테스트 준비를 위해 그래프의 심화 알고리즘에 대해 배웠습니다. 이를 통해 위상 정렬, 강결합 컴포넌트(Kosaraju's Algorithm), 최소 컷 최대 유량(Ford-Fulkerson Algorithm)의 개념과 구현 방법을 익혔습니다. 다음 글에서는 문자열 알고리즘에 대해 알아보겠습니다.

다음 글에서 만나요!