게시글

강좌22 - Algorithm - 3년 전 등록 / 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- . 무단 전재 및 재배포 금지. 출처 표기 시 인용 가능.

댓글

2개의 댓글이 있습니다.
일 년 전
포스팅에서 궁금한 점이 있어 댓글 남깁니다!
평행한 아크가 있는 경우에 굳이 v'을 만들지 않아도 residual network를 그려 문제를 해결할 수 있지 않나요? 제가 참고한 포드-풀커슨 알고리즘을 설명하는 또 다른 포스팅입니다.
https://ratsgo.github.io/data%20structure&algorithm/2017/11/29/maxflow/
직접 해보니 위의 올려주신 예시(평행한 아크가 있는 경우의 예시)의 경우 답이 23이 나왔습니다.
일 년 전
모바일로 볼 때 댓글 다는 UX가 너무 불편합니다 ㅜ
일 년 전
다음에 더 큼직하게 수정하겠습니다!