2020-1ν•™κΈ°, λŒ€ν•™μ—μ„œ β€˜μ•Œκ³ λ¦¬μ¦˜β€™ μˆ˜μ—…μ„ λ“£κ³  κ³΅λΆ€ν•œ λ°”λ₯Ό μ •λ¦¬ν•œ κΈ€μž…λ‹ˆλ‹€. 지적은 μ–Έμ œλ‚˜ ν™˜μ˜μž…λ‹ˆλ‹€ :) 전체 ν¬μŠ€νŠΈλŠ” Algorithm ν¬μŠ€νŠΈμ—μ„œ ν™•μΈν•˜μ‹€ 수 μžˆμŠ΅λ‹ˆλ‹€.

10 minute read

2020-1ν•™κΈ°, λŒ€ν•™μ—μ„œ β€˜μ•Œκ³ λ¦¬μ¦˜β€™ μˆ˜μ—…μ„ λ“£κ³  κ³΅λΆ€ν•œ λ°”λ₯Ό μ •λ¦¬ν•œ κΈ€μž…λ‹ˆλ‹€. 지적은 μ–Έμ œλ‚˜ ν™˜μ˜μž…λ‹ˆλ‹€ :) 전체 ν¬μŠ€νŠΈλŠ” Algorithm ν¬μŠ€νŠΈμ—μ„œ ν™•μΈν•˜μ‹€ 수 μžˆμŠ΅λ‹ˆλ‹€.

이번 ν¬μŠ€νŠΈλŠ” Network Flow 포슀트의 후속 ν¬μŠ€νŠΈμž…λ‹ˆλ‹€. Network Flow 문제의 핡심이 λ˜λŠ” 정리인 <Max-Flow Min-Cut Theorem>에 λŒ€ν•΄ κΆκΈˆν•˜λ‹€λ©΄ 이전 포슀트λ₯Ό μ°Έκ³ ν•΄μ£Όμ„Έμš”! πŸ˜‰

이번 포슀트의 μ½”λ“œλŠ” λ°±μ€€ 6086번: μ΅œλŒ€ μœ λŸ‰ 문제λ₯Ό κΈ°μ€€μœΌλ‘œ μž‘μ„±λ˜μ—ˆμŠ΅λ‹ˆλ‹€ πŸ‘¨β€πŸ’»


Network Flow ν¬μŠ€νŠΈμ—μ„œ μ–΄λ–»κ²Œ Max Flowλ₯Ό ꡬ할지 <Max-Flow Min-Cut Theorem>을 톡해 μ‚΄νŽ΄λ³΄μ•˜λ‹€. 이번 ν¬μŠ€νŠΈμ—μ„œλŠ” Residual Graphλ₯Ό μ‚¬μš©ν•˜λŠ” ν•΄λ‹Ή μ•Œκ³ λ¦¬μ¦˜μ„ 직접 κ΅¬ν˜„ν•΄λ³Έλ‹€.


Ford-Fulkerson Algorithm

사싀 Network Flow ν¬μŠ€νŠΈμ—μ„œ μ„€λͺ…ν•œ Max-Flowλ₯Ό μ°ΎλŠ” 방법을 μ½”λ“œλ‘œ κ΅¬ν˜„ν•œ 것에 λΆˆκ³Όν•˜λ‹€. 큰 λ²”μ£Όλ‘œ 봀을 λ•ŒλŠ” Brute Force Algorithm에 μ†ν•œλ‹€.

1. sourceμ—μ„œ sink둜 κ°€λŠ” μœ λŸ‰μ„ 보낼 수 μžˆλŠ” 경둜 $p$λ₯Ό ν•˜λ‚˜ μ°ΎλŠ”λ‹€. DFS λ˜λŠ” BFSλ₯Ό μ΄μš©ν•˜λ©΄ λœλ‹€.

2. μ°Ύμ•„λ‚Έ 경둜 $p$둜 보낼 수 μžˆλŠ” μ΅œλŒ€ν•œμ˜ μœ λŸ‰μ„ κ΅¬ν•œλ‹€. μ΅œλŒ€ν•œμ˜ μœ λŸ‰μ€ 경둜 $p$λ₯Ό 탐색(traversal)ν•˜λ©° κ°€μž₯ μž‘μ€ 남은 capacityκ°€ λœλ‹€.

3. μ°Ύμ•„λ‚Έ 경둜 $p$에 μ΅œλŒ€ μœ λŸ‰μ„ μ‹€μ œλ‘œ ν˜λ €λ³΄λ‚Έλ‹€. 이 κ³Όμ •μ—μ„œ 순방ν–₯은 μœ λŸ‰μ„ μΆ”κ°€ν•˜κ³ , μ—­λ°©ν–₯은 μœ λŸ‰μ€ λΊ€λ‹€.

예λ₯Ό λ“€μ–΄ μ°Ύμ•„λ‚Έ 경둜 $p$κ°€ $a \rightarrow b \rightarrow c$라면,

// 순방ν–₯
f(a, b) += flow
f(b, c) += flow

// μ—­λ°©ν–₯
f(b, a) -= flow
f(c, b) -= flow

μ£Όλͺ©ν•  점은 [3.] κ³Όμ •μ—μ„œ μ—­λ°©ν–₯을 μ²˜λ¦¬ν•  λ•ŒμΈλ°, λ§Œμ•½ $f(b, a) = 0$μ΄μ—ˆλ‹€λ©΄ $f(b, a) < 0$둜 μŒμˆ˜κ°€ λœλ‹€. 그런데 이런 음수 μœ λŸ‰μ„ ν˜λ €λ³΄λ‚΄λŠ” 것은 κ°€λŠ₯ν•œλ°, $f(b, a)$의 capacityλŠ” $c(b, a) = 0$μ΄λ―€λ‘œ κ²°κ΅­ $f(b, a) < 0 = c(b, a)$둜 μœ λŸ‰μ— λŒ€ν•œ 법칙을 μ „ν˜€ κΉ¨λœ¨λ¦¬μ§€ μ•ŠλŠ”λ‹€!

μ½”λ“œλ‘œ μž‘μ„±ν•˜κΈ° 전에 μ†μœΌλ‘œ 이 μ•Œκ³ λ¦¬μ¦˜μ„ λ”°λΌκ°€λ³΄μž. 이 뢀뢄은 쒋은 μžλ£Œκ°€ μžˆμ–΄μ„œ ν•΄λ‹Ή 자료둜 λŒ€μ²΄ν•˜κ² λ‹€. πŸ™ μ†μœΌλ‘œ ν‘ΈλŠ” Ford-Fulkerson Algorithm


이제 μ½”λ“œλ‘œ μ‚΄νŽ΄λ³΄μž.

✨ Tip: 이 문제의 경우 κ·Έλž˜ν”„λ₯Ό Adjacency List λ³΄λ‹€λŠ” Adjacency Matrix둜 ν‘œν˜„ν•˜λŠ”κ²Œ μ•Œκ³ λ¦¬μ¦˜μ„ 짜기 훨씬 νŽΈν•΄μ§„λ‹€! πŸ˜‰

λ¨Όμ € 문제의 μž…λ ₯을 보면, λ…Έλ“œκ°€ Alphabet λŒ€μ†Œλ¬Έμžλ‘œ λ“€μ–΄μ˜¨λ‹€. 본인은 μ†Œλ¬Έμžλ‘œλ„ λ“€μ–΄μ˜¨λ‹€λŠ” κ±Έ λ‚˜μ€‘μ— κΉ¨λ‹¬μ•˜λ‹€ 😱 μž…λ ₯을 μ •κ·œν™”ν•˜κΈ° μœ„ν•΄μ„  'A'둜 λΉΌμ£Όλ©΄ λœλ‹€. 그러면 λ…Έλ“œλŠ” [A-Z]: [0, 26], [a-z]: [32, 57]의 번호λ₯Ό κ°–κ²Œ λœλ‹€.

μš°λ¦¬λŠ” int capacity[][]λΌλŠ” 배열에 νŒŒμ΄ν”„μ— 흐λ₯Ό 수 μžˆλŠ” μœ λŸ‰μ˜ capacityλ₯Ό κΈ°λ‘ν•œλ‹€. κ·Έλž˜μ„œ μž…λ ₯을 톡해 Graphλ₯Ό κ΅¬μΆ•ν•˜λ©΄ μ•„λž˜μ™€ κ°™λ‹€.

#define MAX 80

int capacity[MAX][MAX];

for (int i = 0; i < N; i++) {
  char s, e;
  int c;
  cin >> s >> e >> c;
  capacity[s - 'A'][e - 'A'] += c;
  capacity[e - 'A'][s - 'A'] += c;
}

이제 μ€€λΉ„λŠ” 끝났고, 본격적으둜 <\Ford-Fulkerson Algorithm>을 κ΅¬ν˜„ν•΄λ³΄μž.

long long FordFulkerson(int source, int sink) {
  long long ret = 0;

  // find path and update residual graph
  while (1) {
    ...
    // dfs
    while (!s.empty()) {
      ...
    }

    // escape: no possible path
    if (Prev[sink] == -1) break;

    // find possible max-flow

    // flow the max-flow

    total_flow += flow;
  }

  return total_flow;
}

λ¨Όμ € dfs κ΅¬ν˜„ 뢀뢄을 μ‚΄νŽ΄λ³΄μž.

  int Prev[MAX];
  fill(Prev, Prev + MAX, -1);
  Prev[source] = source;

  stack<int> s;
  s.push(source);

  // dfs
  while (!s.empty()) {
    int curr = s.top();
    s.pop();

    if(curr == sink) break;

    for (int i = 0; i < MAX; i++) {
      if (Prev[i] == -1 && capacity[curr][i] > 0) {
        s.push(i);
        Prev[i] = curr;
      }
    }
  }

  // escape: no possible path
  if (Prev[sink] == -1) break;

stack<int>λ₯Ό μ΄μš©ν•΄ DFSλ₯Ό κ΅¬ν˜„ν–ˆμœΌλ©°, Prev[]에 path historyλ₯Ό κΈ°λ‘ν•œλ‹€. λ§Œμ•½ sink에 λ„λ‹¬ν–ˆλ‹€λ©΄, κ·Έλž˜ν”„ 탐색을 μ’…λ£Œν•œλ‹€. λ§Œμ•½ sink에 λ„λ‹¬ν•˜μ§€ λͺ» ν–ˆλ‹€λ©΄ 즉 sink둜 κ°€λŠ” 경둜λ₯Ό 찾지 λͺ» ν–ˆλ‹€λ©΄, Prev[sink]의 값이 κ°±μ‹ λ˜μ§€ μ•ŠμœΌλ―€λ‘œ Prev[sink] == -1이 λœλ‹€. 이 경우라면, μ•Œκ³ λ¦¬μ¦˜μ„ μ’…λ£Œν•œλ‹€.

사싀 μœ„μ˜ μ•Œκ³ λ¦¬μ¦˜μ€ μ•„λž˜μ™€ 같이 졸큼 κ°œμ„ ν•  수 μžˆλ‹€.

  int Prev[MAX];
  fill(Prev, Prev + MAX, -1);
  Prev[source] = source;

  stack<int> s;
  s.push(source);

  // dfs
  while (!s.empty()) {
    int curr = s.top();
    s.pop();

    for (int i = 0; i < MAX; i++) {
      if (Prev[i] == -1 && capacity[curr][i] > 0) {
        s.push(i);
        Prev[i] = curr;

        if (i == sink) break;
      }
    }

    if (Prev[sink] != -1) break;
  }

  // escape: no possible path
  if (Prev[sink] == -1) break;

λ‹€λ§Œ 처음의 μ½”λ“œμ²˜λŸΌ κ΅¬ν˜„ν•΄λ„ ν†΅κ³Όν•˜κΈ° λ•Œλ¬Έμ— 크게 μ‹ κ²½μ“°μ§€λŠ” 말자.


λ‹€μŒμ€ 찾은 경둜λ₯Ό μ΄μš©ν•΄ κ·Έλž˜ν”„μ— 흘릴 μœ λŸ‰μ„ μ°Ύμ•„μ•Ό ν•œλ‹€. 이것은 μ•„λž˜μ˜ μ½”λ“œλ‘œ μˆ˜ν–‰ν•  수 μžˆλ‹€.

  // find possible max-flow
  int flow = INT_MAX;
  for (int v = sink; v != source; v = Prev[v]) {
    flow = min(flow, capacity[Prev[v]][v]);
  }

for (int v = sink; v != source; v = Prev[v]) νŒ¨ν„΄μ€ κ·Έλž˜ν”„ νƒμƒ‰μ—μ„œ 경둜λ₯Ό μž¬κ΅¬μ„± ν•  λ•Œ 자주 μ“°λŠ” ν…Œν¬λ‹‰μ΄λ―€λ‘œ μˆ™μ§€ ν•˜λ„λ‘ ν•˜μž. πŸ™Œ


λ‹€μŒμ€ κ²½λ‘œμ— μœ λŸ‰ flowλ₯Ό 흐λ₯΄κ²Œ ν•˜λŠ” μž‘μ—…μ΄λ‹€. λ§ˆμ°¬κ°€μ§€λ‘œ 경둜λ₯Ό μž¬νƒμƒ‰ν•˜λ©° μœ λŸ‰μ„ ν˜λ €λ³΄λ‚΄λ©΄ λœλ‹€.

  // flow the max-flow
  for (int v = sink; v != source; v = Prev[v]) {
    capacity[Prev[v]][v] -= flow;
    capacity[v][Prev[v]] += flow;
  }

  // update total flow!
  total_flow += flow;

μ΄λ•Œ, μ—­λ°©ν–₯μœΌλ‘œλŠ” capacityκ°€ λŠ˜μ–΄λ‚œλ‹€λŠ” 사싀에 μœ μ˜ν•˜μž.


μ‹œκ°„ λ³΅μž‘λ„

μœ„μ˜ 그림은 <Ford-Fulkerson Algorithm>μ—μ„œ μ΅œμ•…μ˜ μƒν™©μ˜ μ˜ˆμ‹œμ΄λ‹€. DFS둜 경둜λ₯Ό μ°ΎλŠ” 맀 μ‹œν–‰λ§ˆλ‹€ μš©λŸ‰ 1의 κ°€μš΄λ° 간선을 μ§€λ‚œλ‹€κ³  ν•˜μž. 그러면 μš©λŸ‰ 1,000을 μ±„μš°κΈ° μœ„ν•΄ 1,000은 iteration을 μˆ˜ν–‰ν•΄μ•Ό ν•œλ‹€. 이것은 DFS둜 경둜λ₯Ό νƒμƒ‰ν•˜λŠ” <Ford-Fulkerson Algorithm>의 ν•œκ³„μ΄λ‹€ πŸ˜₯

μœ„μ˜ 상황을 λ°”νƒ•μœΌλ‘œ <Ford-Fulkerson Algorithm>의 μ‹œκ°„ λ³΅μž‘λ„λ₯Ό μœ λ„ν•΄λ³΄μž. κ·Έλž˜ν”„ $G_f$μ—μ„œ μ΅œλŒ€ μš©λŸ‰μ΄ $f_{\max}$라고 ν•˜μž. ν•œλ²ˆμ˜ DFS νƒμƒ‰μœΌλ‘œ 흘릴 수 μžˆλŠ” μœ λŸ‰μ˜ μ΅œμ†Ÿκ°’μ€ 1μ΄λ―€λ‘œ 총 $f_{\max}$번의 DFSλ₯Ό μˆ˜ν–‰ν•΄μ•Ό ν•œλ‹€. μ΄λ•Œ, DFS의 μ‹œκ°„λ³΅μž‘λ„κ°€ $O(V + E)$μ΄λ―€λ‘œ, <Ford-Fulkerson Algorithm>은 $O((V + E) f_{\max})$ 만큼의 μ‹œκ°„λ³΅μž‘λ„λ₯Ό 가진닀! λ§Œμ•½ μ •μ μ˜ 갯수 $V$κ°€ λ¬΄μ‹œν•  만큼 적닀면 $O(E \cdot f_{\max})$라고 적기도 ν•œλ‹€.


Edmonds-Karp Algorithm

μ•žμ„  <Ford-Fulkerson Algorithm>의 μ½”λ“œμ—μ„œλŠ” DFSλ₯Ό 톡해 문제λ₯Ό ν•΄κ²°ν–ˆλ‹€. μ΄λ•Œ, 간선을 μ°ΎλŠ” 과정을 BFS둜 μˆ˜ν–‰ν•œλ‹€λ©΄, <Edmonds-Karp Algorithm>이 λœλ‹€!

<Edmonds-Karp Algorithm>은 κΈ°μ‘΄ <Ford-Fulkerson Algorithm>이 μ΅œλŒ€ μš©λŸ‰ $f_{\max}$κ°€ 큰 κ²½μš°μ— 잘 λ™μž‘ν•˜μ§€ λͺ»ν•œλ‹€λŠ” 점 λ•Œλ¬Έμ— μ œμ‹œλœ μ•Œκ³ λ¦¬μ¦˜μ΄λ‹€. 그런데 DFSμ—μ„œ BFS둜 λ°”κΎΈλ©΄ 무엇이 λ‹¬λΌμ§€λŠ” 걸까?

λ‹€μ‹œ μœ„μ˜ 예제λ₯Ό 톡해 μ‚΄νŽ΄λ³΄μž.

일단 λ§¨μ²˜μŒμ—λŠ” A - B - C - D의 경둜둜 μœ λŸ‰μ΄ ν˜λ €λ‹€κ³  ν•˜μž. κ·Έ λ‹€μŒμ— 흐λ₯Ό μœ λŸ‰μ„ μ‚΄νŽ΄λ³΄λ©΄,

  1. 방문: [A], 큐: [B, C]
  2. λ°©λ¬Έ: [A, B], 큐: [D] (B -> CλŠ” 이미 μš©λŸ‰μ΄ λ‹€ μ°ΌκΈ° λ•Œλ¬Έμ— 도달할 수 μ—†λ‹€)
  3. 방문: [A, B, D], 큐: []
  4. 999만큼의 μœ λŸ‰μ„ ν˜λ €λ³΄λ‚Έλ‹€.

이 과정을 λ°˜λ³΅ν•˜λ©΄ 기쑴의 <Ford-Fulkerson Algorithm> 보닀 훨씬 적은 iteration으둜 μ΄μœ λŸ‰μ„ ꡬ할 수 μžˆλ‹€.

<Edmonds-Karp Algorithm>은 flow의 κ°’λ³΄λ‹€λŠ” edge $E$에 더 영ν–₯을 λ°›κ²Œ λœλ‹€. μžμ„Έν•œ 증λͺ…은 κ΅¬μ‚¬κ³Όλ‹˜μ˜ λΈ”λ‘œκ·Έλ₯Ό 톡해 μ‚΄νŽ΄λ³΄μž πŸ˜‰ λ‚˜μ€‘μ— μ •λ¦¬ν•˜κ² μŠ΅λ‹ˆλ‹€β€¦

결둠은 <Edmonds-Karp Algorithm>이 $O(VE^2)$의 μ‹œκ°„λ³΅μž‘λ„λ₯Ό 가진닀!!


μ΄κ²ƒμœΌλ‘œ λ„€νŠΈμ›Œν¬ ν”Œλ‘œμš° 문제의 기본적인 두 μ•Œκ³ λ¦¬μ¦˜μΈ <Ford-Fulkerson Algorithm>κ³Ό <Edmonds-Karp Algorithm>을 μ‚΄νŽ΄λ³΄μ•˜λ‹€. 두 μ•Œκ³ λ¦¬μ¦˜μ˜ μ‹œκ°„λ³΅μž‘λ„κ°€ λ‹€λ₯΄κΈ° λ•Œλ¬Έμ— 상황에 맞게 μ μ ˆν•˜κ²Œ 선택해 μ‚¬μš©ν•˜λ©΄ λœλ‹€.

λ‹€μŒ ν¬μŠ€νŠΈλ‘œλŠ” λ„€νŠΈμ›Œν¬ ν”Œλ‘œμš°λ₯Ό μ΄μš©ν•΄ ν•΄κ²°ν•  수 μžˆλŠ” λ¬Έμ œλ“€μ— λŒ€ν•΄ 닀룬닀. λŒ€ν‘œμ μΈ 문제둜 <Bipartite Matching; 이뢄 맀칭>κ³Ό λ„€νŠΈμ›Œν¬ ν”Œλ‘œμš°μ— μ œμ•½(constraint)λ₯Ό μΆ”κ°€ν•œ λ²„μ „μ˜ λ¬Έμ œλ“€μ„ μ‚΄νŽ΄λ³Ό μ˜ˆμ •μ΄λ‹€ πŸ™Œ

πŸ‘‰ Bipartite Matching


references

Categories:

Updated: