안녕하세요. 이번 시간에는 그래프 마지막 강좌 네트워크 플로우에 대해서 알아보겠습니다. 네트워크 플로우란 기존 그래프에서 아크에 용량 제한이 있는 경우입니다.
예전 그래프 시간에 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이라고 치면 됩니다. 신기하죠?
이상으로 알고리즘 기본 개념 강좌를 마칩니다. 다음 시간부터는 유명한 문제들을 자바스크립트로 풀어보겠습니다.
익명
