이 블로그는 광고 클릭 수익으로 운영됩니다!
괜찮으시다면 광고 차단을 풀어주세요 ㅠㅠ

게시글

강좌22 - Algorithm - 2년 전 등록 / 2달 전 수정

네트워크 플로우(network flow)

조회수:
0
이 블로그는 광고 클릭 수익으로 운영됩니다!
괜찮으시다면 광고 차단을 풀어주세요 ㅠㅠ
이 블로그는 광고 클릭 수익으로 운영됩니다!
괜찮으시다면 광고 차단을 풀어주세요 ㅠㅠ

안녕하세요. 이번 시간에는 그래프 마지막 강좌 네트워크 플로우에 대해서 알아보겠습니다. 네트워크 플로우란 기존 그래프에서 아크에 용량 제한이 있는 경우입니다.

예전 그래프 시간에 Arc에 capacity라는 매개변수를 등록해두었죠. 이 때 쓰기 위함이었습니다. 이 강좌는 그래프 시간 코드를 바탕으로 합니다.

네트워크 플로우가 어디에 쓰이는지 궁금하시죠? 쉽게 설명하면 물이 시작점에서 끝점으로 흐를 때 최대 얼마나 많은 물이 흐를 수 있는 지 구하는 겁니다.

물 대신 물건으로 바꾸면 택배 시스템같은 곳에서도 사용될 수 있습니다. 버텍스들을 도시로, 아크들을 도로로 바꿔 생각하면 물류 시스템이 되는 거죠. 또 전혀 의외의 곳에서도 사용될 수 있습니다. 

 

왼쪽을 남자, 오른쪽을 여자라고 치면 서로서로 원하는 남녀 최다 쌍을 구할 때도 네트워크 플로우를 사용할 수 있습니다. 매칭 시스템에서 유용하겠죠. 어떻게 할 수 있는지는 마지막에 알려드립니다.

네트워크 플로우의 개념을 그림으로 보겠습니다.

 

왼쪽 그래프에서 s가 시작점이고 t가 끝점입니다. 아크의 숫자는 용량 제한(capacity)를 뜻합니다. s에서 w로 갈 때는 최대 3의 물이 흐를 수 있고, z에서 t로 갈 때는 최대 2의 물이 흐를 수 있다는 뜻입니다.

오른쪽의 그래프는 실제로 물이 흐르고 있는 것을 뜻합니다. 슬래쉬(/) 앞의 숫자가 실제 흐르는 물입니다. 1/3은 3의 용량 제한 중 1만큼 물이 흐르고 있다는 뜻이고, 그냥 3은 0/3을 뜻합니다. 물이 안 흐르는 상태이죠.

이제 어떻게 최대 유량을 구할까요? 바로 포드 풀커슨의 알고리즘을 사용합니다. 

그 전에 한 가지 제약 사항을 알려드리겠습니다. 네트워크 플로우에서는 평행한 아크가 있으면 안 됩니다. 아래 왼쪽 그림에서 v1과 v2이 서로에게 물을 전달하는 것을 뜻합니다.

 

이런 경우는 오른쪽 그림같이 가상의 v'라는 버텍스를 만들어 평행하지 않게 만들면 됩니다. 이건 그냥 눈속임이나 다름없지만 이 작업이 반드시 필요합니다.

포드 풀커슨에서는 잔여 네트워크(residual network)라는 것을 사용합니다. 아래 그림에서 잔여 네트워크와 계산 과정을 설명하겠습니다.

 

일단 첫 번째 그림이 처음 상태입니다. 오른쪽 그림은 첫 번째 그림의 잔여 네트워크입니다. 어떻게 잔여 네트워크로 바뀐 거냐면요. s에서 w로 가는 아크가 1/3이잖아요? 기존에 흐르던 1을 반대 방향으로 바꾸고, 빈 공간(3 - 1 = 2)을 원래 방향으로 보내면 됩니다. w에서 x도 기존에 흐르던 2를 반대 방향으로 바꾸고, 빈 공간(2 - 2 = 0)은 없으므로 생략합니다. x에서 t도 기존에 흐르던 2를 반대방향으로 바꾸고, 빈 공간(3 - 2 = 1)을 원래 방향으로 보내줍니다.

 

잔여 네트워크에서 s에서 t로 가는 선이 생기는데요. 이 경로를 통해서 1만큼 더 보내줄 수 있다는 걸 의미합니다. 신기하죠? 1만큼씩 늘려주면 아래 왼쪽같은 그래프가 됩니다.

 

w에서 y는 잔여 네트워크에서 1 늘려주는 방향과 반대로 흐르고 있었기 때문에, 더해주는 대신 1을 뺍니다. 이제 새로 증강한 그래프에서 다시 잔여 네트워크를 구하면 위 오른쪽 그림 Gf와 같습니다. 하지만 더는 s에서 t로 가는 경로를 찾을 수 없기에, 흐름을 늘려줄 곳이 없음을 확인할 수 있습니다.

따라서 최대 유량은 x->t의 3과 z->t의 1을 합친 4입니다. 이걸 코드로 구현해보겠습니다. 벌써부터 눈앞이 캄캄해지는군요.

Graph.prototype.fordFulkerson = function(start, end) {
  function ReArc(data, dest) { // 잔여 아크 생성자 선언
    this.data = data || 0;
    this.destination = dest;
    this.reverse = null;
  }
  var vertex = this.first;
  while (vertex) { // 모든 아크에 잔여 아크를 추가하는 작업
    var arc = vertex.arc;
    while (arc) {
      var reArc = new ReArc(arc.capacity - arc.data, arc.destination);
      var reArc2 = new ReArc(arc.data, vertex);
      reArc.reverse = reArc2; // 두 잔여 아크는 서로 역방향의 관계
      reArc2.reverse = reArc;
      vertex.residual = vertex.residual || [];
      vertex.residual.push(reArc);
      arc.destination.residual = arc.destination.residual || [];
      arc.destination.residual.push(reArc2);
      arc = arc.nextArc;
    }
    vertex = vertex.next;
  }
  var self = this;

  function findArcInPath(path, reArc, start) { // 잔여 아크가 이미 지나온 경로 안에 있는지 찾는 함수
    for (var i = 0; i < path.length; i++) {
      if (path[i][0] === reArc || reArc.destination === path[i][2]) {
         return true;
      }
    }
    return false;
  }

  function findPath(from, to, path) { // 잔여 네트워크의 경로를 재귀적으로 찾는 함수
    if (from === to) return path;
    vertex = self.first;
    var reArcs;
    var arc;
    while (vertex) {
      if (vertex.key === from) 
        reArcs = vertex.residual;
        arc = vertex.arc;
        break;
      }
      vertex = vertex.next;
    }
    for (var i = 0; i < reArcs.length; i++) { // 잔여 아크 전체를 탐색
      var residual = reArcs[i].data;
      if (residual > 0 && !findArcInPath(path, reArcs[i], vertex)) { // 잔여 아크 용량이 1 이상이고 지나온 패스에 없으면
         var pathCopy = path.slice();
         pathCopy.push([reArcs[i], arc, vertex]);
        var result = findPath(reArcs[i].destination.key, to, pathCopy); // 재귀적으로 다음 패스를 찾음
        if (result) return result;
      }
    }
    return null;
  }

  var path = findPath(start, end, []);
  while (path) { // 잔여 네트워크에 경로가 없을 때까지 반복적으로 찾고 증강
    var flow = Infinity;<
    for (var i = 0; i < path.length; i++) {
      if (path[i][0].data < flow) flow = path[i][0].data; // 추가할 수 있는 물의 양 찾기
    }
    for (var i = 0; i < path.length; i++) {
      path[i][0].data -= flow; // 잔여 아크에 흐름 뺌
      path[i][0].reverse.data += flow; // 잔여 역아크에 흐름 추가
      path[i][1].data += flow; // 아크에 흐름 추가
    }
    path = findPath(start, end, []);
  }
  var sum = 0;
  vertex = self.first;
  while (vertex) { // 마지막으로 시작점의 유량을 체크하면 
    if (vertex.key === start) {
      arc = vertex.arc;
      while (arc) {
        sum += arc.data;
        arc = arc.nextArc;
      }
      break;
    }
    vertex = vertex.next;
  }
  return sum;
};
var graph = new Graph();
graph.insertVertex('s');
graph.insertVertex('w');
graph.insertVertex('y');
graph.insertVertex('x');
graph.insertVertex('z');
graph.insertVertex('t');
graph.insertArc(1, 's', 'w', 3);
graph.insertArc(2, 'w', 'x', 2);
graph.insertArc(2, 'x', 't', 3);
graph.insertArc(2, 's', 'y', 2);
graph.insertArc(1, 'y', 'w', 3);
graph.insertArc(1, 'x', 'y', 1);
graph.insertArc(2, 'y', 'z', 3);
graph.insertArc(1, 'z', 'x', 3);
graph.insertArc(1, 'z', 't', 2);
graph.fordFulkerson('s', 't'); // 4

후... 긴 강의가 끝났네요. 이제 맨 위의 남녀 매칭 문제의 정답을 공개합니다.

 

위와 같이 그래프에 시작점과 끝점을 추가한 뒤 포드 풀커슨 방법으로 물을 흘려보내서 최대 유량을 구하면 그게 바로 최다 매칭 쌍입니다. 각 아크는 capacity가 1이라고 치면 됩니다. 신기하죠?

이상으로 알고리즘 기본 개념 강좌를 마칩니다. 다음 시간부터는 유명한 문제들을 자바스크립트로 풀어보겠습니다.

목록
투표로 게시글에 관해 피드백을 해주시면 많은 도움이 됩니다. 오류가 있다면 어떤 부분에 오류가 있는지도 알려주세요! 잘못된 정보가 퍼져나가지 않도록 도와주세요.
Copyright © 2016- 무단 전재 및 재배포 금지

댓글

아직 댓글이 없습니다.