[백준 2365번] 숫자판 만들기 (Python3)

from collections import *

def BFS(x):
  parent = [-1]*K
  dq = deque([0])
  while dq:
    now = dq.popleft()
    for next in range(K):
      if (c:=graph[now][next])<0:
        c = x
      if parent[next]<0 and c-flow[now][next]:
        parent[next] = now
        if next==N+1:
          return parent
        dq.append(next)

def solve(x):
  global flow
  flow = [[0]*K for i in range(K)]
  s = 0
  while parent:=BFS(x):
    now = N+1; f = M
    while now:
      last = parent[now]
      if (c:=graph[last][now])<0:
        c = x
      f = min(f,c-flow[last][now])
      now = last
    now = N+1
    while now:
      last = parent[now]
      flow[last][now] += f; flow[now][last] -= f
      now = last
    s += f
  if S==s:
    return flow

N = int(input()); M = 1<<14; K = N*2+2
graph = [[0]*K for i in range(K)]
column,row = [[*map(int,input().split())] for i in range(2)]
S = sum(column)
for i in range(1,N+1):
  graph[0][i] = column[i-1]
  graph[-i][N+1] = row[i-1]
  for j in range(1,N+1):
    graph[i][-j] = -1

x,c = M,13
while c+1:
  if result:=solve(x):
    X,Flow = x,result
    x -= 1<<c
  else:
    x += 1<<c
  if not c:
    if result:=solve(x):
      X,Flow = x,result
  c -= 1    
print(X)
for i in range(1,N+1):
  print(*reversed(Flow[i][-N:]))

최대유량 + 이분탐색으로 해결하였다.

 

풀이를 설명하면,

1. source - 행 - 열 - sink로 이어지는 그래프를 만든다. 이때 source-행, 열-sink의 용량은 각 행,열의 합과 같고 행-열의 용량은 -1로 둔다.

2. solve(x) 함수는 1에서 -1로 둔 용량을 x로 취급하여 최대유량을 찾는 함수이다. 이때 유량이 S (모든 행 또는 모든 열의 합)과 같으면 true, 다르면 false이다.

3. 이분탐색을 통해 solve(x) 함수가 true를 반환하는 가장 작은 x를 찾는다.

 

 

오늘의 교훈) 최대유량은 다양한 방식으로 활용할 수 있다.