[백준 17412번] 도시 왕복하기 1 (Python3)

import sys
from collections import *
def input(): return map(int,sys.stdin.readline().split())

def BFS():
  f = 1e9; visited = [-1]*N
  dq = deque([(0,0)])
  while dq:
    now,last = dq.popleft()
    if visited[now]<0:
      visited[now] = last
      if now==1:
        return f,visited
      for next in graph[now]:
        if (dif:=graph[now][next]-flow[now][next]):
          f = min(dif,f)
          dq.append((next,now))

def solve():
  while bfs:=BFS():
    f,visited = bfs
    now = 1
    while now:
      last = visited[now]
      flow[last][now] += f; flow[now][last] -= f
      now = last

N,M = input()
graph = [{} for i in range(N)]
for _ in range(M):
  a,b = input()
  graph[a-1][b-1] = 1; graph[b-1][a-1] = 0
flow = [[0]*N for i in range(N)]
solve()
print(sum(flow[i][1] for i in range(N)))

네트워크 플로우 기본문제

개념은 https://m.blog.naver.com/kks227/220804885235 을 참고하였다.