백준 1298번 문제(노트북의 주인을 찾아서) 파이썬(Python) 풀이 [로밍맨]

문제 링크

www.acmicpc.net/problem/1298

1298번: 노트북의 주인을 찾아서

 

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

import sys
import collections
import math
 
SOURCE = 0
SINK = 201
VMAX = 202
HUND = 100
 
def bfs(flow, capacity, source, sink):
  parent = [-1] * VMAX
  q = collections.deque([source])
  parent[source] = source
  while len(q) != 0:
    item = q.popleft()
    for i in range(VMAX):
      if parent[i] == -1 and capacity[item][i] - flow[item][i]:
        q.append(i)
        parent[i] = item
  return parent
 
def maxFlow(capacity, source, sink):
  flow = [[0] * VMAX for _ in range(VMAX)]
  rst = 0
  while True:
    parent = bfs(flow, capacity, source, sink)
    if parent[sink] == -1:
      return rst
    #minimum
    node = sink
    m = math.inf
    while node != source:
      m = min(m, capacity[parent[node]][node] - flow[parent[node]][node])
      node = parent[node]
    #add
    rst += m
    node = sink
    while node != source:
      flow[parent[node]][node] += m
      flow[node][parent[node]] -= m
      node = parent[node]
 
def solve():
  N, M = map(int, sys.stdin.readline().rstrip().split())
  graph = [[0] * VMAX for _ in range(VMAX)]
  for _ in range(M):
    a, b = map(int, sys.stdin.readline().rstrip().split())
    graph[a][b+HUND] += 1
  for i in range(1, HUND+1):
    graph[SOURCE][i] += 1
    graph[i+HUND][SINK] += 1
  print(maxFlow(graph, SOURCE, SINK))
 
solve()
 

 

728x90

 

전형적인 이분 매칭 문제로, 최대 유량 문제로 변환하여 풀 수 있습니다.

이분 매칭 문제와 최대 유량 문제는 아직도 많은 연구자들이 연구하고 있는 분야이며, 불과 몇 년 전에도 새로운 알고리즘이 개발되었습니다.

실제 응용되는 분야가 굉장히 많은 알고리즘임에도 불구하고, 일반적인 기업들의 코딩테스트에는 잘 등장하지 않는데요.

그 이유는 사실상 풀이를 외워야 하고, 최대 유량 알고리즘을 활용하지 않는 분야에서는 이 알고리즘을 알아야 할 이유도 없기 때문입니다.

다시 말해서 중요하고 응용 가능성이 매우 높지만, 일반적인 개발자들에게는 특별히 많이 사용되지 않기 때문이라고 할 수 있습니다.

최대 유량 문제를 풀기 위한 알고리즘은 매우 많지만 실제 대회나 코테에서는 Edmonds-Karp 알고리즘 정도만 사용해도 보통 풀리기 때문에 저는 보통 Edmonds-Karp 알고리즘을 사용합니다.

 

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

www.youtube.com/watch?v=RHyFfFUXHZE  

 

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