[백준 1031번] 스타 대결 (Python)

from collections import *

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

def update(i,j):
  dq = deque([i]); parent = [-1]*K
  while dq:
    now = dq.popleft()
    for next in adj[now]:
      if 0<next<i or now==i and next<=j or parent[next]!=-1:
        continue
      if graph[now][next]-flow[now][next]:
        parent[next] = now
        dq.append(next)
        if next==j:
          return parent

[N,M],row,column = [[*map(int,input().split())] for i in range(3)]; K = N+M+2
graph,flow = [[[0]*K for i in range(K)] for i in range(2)]
adj = [[] for i in range(K)]
for i in range(1,N+1):
  graph[0][i] = row[i-1]
  adj[0].append(i); adj[i].append(0)
  for j in range(1,M+1):
    graph[i][j+N] = 1
    adj[i].append(j+N); adj[j+N].append(i)
for j in range(1,M+1):
  graph[j+N][K-1] = column[j-1]
  adj[j+N].append(K-1); adj[K-1].append(j+N)
while parent:=BFS():
  now = K-1
  while now:
    last = parent[now]
    flow[last][now] += 1; flow[now][last] -= 1
    now = last
if sum(flow[0])==sum(column)==sum(row):
  for i in range(1,N+1):
    for j in range(N+1,N+M+1):
      if flow[i][j] and (parent:=update(i,j)):
        flow[i][j] -= 1
        while j!=i:
          last = parent[j]
          flow[last][j] += 1; flow[j][last] -= 1
          j = last
  for i in range(1,N+1):
    print(*flow[i][N+1:-1],sep="")
else:
  print(-1)

최대유량 응용문제

최대유량으로 격자를 배치하는건 간단하지만 이를 사전순으로 정렬하는게 까다로운 문제이다.

 

풀이를 설명하면,

1. source-지민팀-현수팀-sink의 그래프를 그린다. 이때 source-지민팀의 용량과 현수팀-sink의 용량은 각자의 경기수이고, 지민팀-현수팀의 용량은 1이다.

2. 에드몬드-카프로 최대유량을 구한다.

3. update(i,j) 함수는 i-j의 유량이 존재할 경우 i-j 간선을 거치지 않고 다른 방향으로 i>j로 유량 1을 흘릴 수 있는지 찾고, 가능하다면 해당 경로대로 유량을 흘리고, i-j 유량을 0으로 만드는 함수이다.

4. 3의 BFS 과정에서 i보다 작은(사전순으로 앞서는) 정점이나, i와 연결된 j보다 작은 간선을 고려해선 안된다.

5. 사전순으로 앞서는 flow부터 update 함수를 실행하여 유량이 존재하면 0으로 만들어주어 사전순으로 가장 작은 값을 출력한다.

 

처음에는 이 문제를 MCMF로 풀려고 시도했었다. 간선의 용량을 사전순으로 크기가 커지도록 한 뒤 최소비용을 구하려 했는데, 이 방법을 이용할 경우 예외가 발생하지 않기 위해서 간선의 용량이 기하급수적으로 커져야한다는 것을 알고 포기하게 되었다. 

최대유량의 이해도를 높일 수 있는 좋은 문제였다.