백준 6086번 문제(최대 유량) 파이썬(Python) 풀이 [로밍맨]

문제 링크

https://www.acmicpc.net/problem/6086

6086번: 최대 유량

 

정답 코드는 아래와 같습니다.

import math
 
sz = 128
 
def bfs(flow, capacity, source, sink):
  q = [source]
  parent = [-1] * sz
  parent[source] = source
  while len(q) != 0:
    item = q.pop(0)
    for i in range(sz):
      if parent[i] == -1 and capacity[item][i] - flow[item][i] > 0:
        q.append(i)
        parent[i] = item
  return parent
 
def maxFlow(capacity, source, sink):
  flow = [[0] * sz for _ in range(sz)]
  rst = 0
  while True:
    parent = bfs(flow, capacity, source, sink)
    if parent[sink] == -1:
      return rst
    p = sink
    amount = math.inf
    while p != source:
      amount = min(amount, capacity[parent[p]][p] - flow[parent[p]][p])
      p = parent[p]
    rst += amount
    p = sink
    while p != source:
      flow[parent[p]][p] += amount
      flow[p][parent[p]] -= amount
      p = parent[p]
 
def solve():
  n = int(input())
  capacity = [[0] * sz for _ in range(sz)]
  for _ in range(n):
    p, q, c = input().split()
    p = ord(p)
    q = ord(q)
    c = int(c)
    capacity[p][q] += c
    capacity[q][p] += c
  print(maxFlow(capacity, ord('A'), ord('Z')))
 
solve()
 

 

최대 유량 문제는 실제 세상에서 많이 활용되는 중요한 문제입니다.

이분 매칭 문제를 최대 유량 문제로 전환하여 해결한다는 점을 고려한다면, 실제 세상의 정말 많은 문제가 최대 유량 문제임을 알 수 있습니다.

따라서 최근까지도 계속해서 많은 연구자들이 연구하고 있는 분야입니다.

 

728x90

 

우리 생활과 밀접(?)한 예를 한 번 들어보겠습니다.

도시에 재난이 발생하여 시민들을 여러 곳에 위치한 피난처로 대피시켜야 합니다. 그런데 각 피난처에는 수용할 수 있는 인원이 제한적입니다. 정부에서는 각 시민들에게 어느 위치의 피난처로 이동해야 하는지 알려주어야 합니다. 만일 그렇지 않으면 각 시민들은 피난처에 효율적으로 배치되지 못하기 때문에 어떤 피난처에는 너무 많은 사람이 몰려서 피난처에 도착하여도 보호받지 못하는 사람이 생길 것이고, 어떤 피난처에는 너무 적은 사람이 몰려서 불필요하게 피난처의 공간이 낭비될 것입니다.

"도시", "피난처" 라고 했지만, "영화관/선박/아파트", "출구" 와 같이 바꿀 수도 있습니다. 전형적인 이분매칭/최대유량 문제입니다. 이 외에도 실제 세상에는 정말 많은 최대유량 문제가 존재합니다.

 

이처럼 실질적으로 중요한 문제임이 분명하고, 지속적으로 연구하고 있는 문제이지만, 실제 기업의 코딩테스트에는 잘 등장하지 않습니다. 그 이유는 내용이 어려워서 문제가 전형적이기 때문입니다.

수능 수학 문제를 생각해보면, 가장 어려운 문제는 개념 자체는 오히려 쉬운 "확률" 과 같은 단원에서 출제됩니다. "적분"과 같이 상대적으로 내용이 어려운 단원에서는 응용하여 문제를 만들면 거의 아무도 풀지 못하기 때문에 어려운 단원의 문제는 오히려 쉽고(전형적이고), 쉬운 단원의 문제는 오히려 어렵습니다.

최대 유량 문제는 내용 자체가 어렵습니다. 따라서 쉽게 출제하기 마련입니다. 그러다보니 공부를 한 사람이라면 어렵지 않게 풀 수 있고, 공부를 하지 않았다면 (특별한 천재가 아닌 이상) 그 순간에 풀이를 생각해내서 풀어낼 수 없습니다. 언뜻 보면 공부를 한 사람이 풀 수 있고, 안 한 사람이 풀 수 없는 문제라면 공정한 것 아닌가 생각할 수도 있지만, 기업은 공정하게 인재를 선발하는 것 보다는 창의적인 인재를 뽑는 것에 더욱 가중치를 둔다는 것을 고려했을 때, 최대유량 문제는 그닥 매력적인 문제가 아닙니다.

그렇다고 해서 최대유량 문제가 전혀 출제되지 않는 것은 아니므로 구직자 입장에서는 반드시 익혀야 하는 문제임은 틀림없습니다.

 

최대 유량 문제의 가장 핵심은 A -> B 로 x 만큼 흐르는 것은 B -> A 로 -x 만큼 흐르는 것과 같다는 것을 이해하는데 있습니다. 어떤 사람에게는 너무 당연하고 쉽게 이해되는 개념이지만, 어떤 사람에게는 도대체 무슨 소리인지 아무리 생각해봐도 이해가 되지 않는 개념입니다.

마치 중학교 1학년 때 처음 배우는 음수의 개념을 이해하는 것과 비슷합니다. 스스로 납득이 될 때까지 곱씹으면서 생각해보시길 추천드립니다.

 

풀이는 아래 영상을 참고 바랍니다.

https://www.youtube.com/watch?v=p3Z43-5KVjQ 

 

저작권 라이선스: CC BY (출처만 표시하면 자유롭게 이용 가능)