백준 17412 - 도시 왕복하기 1 (Python)

네트워크 플로우 문제입니다.
너무 어려운 문제라 다른 분들의 풀이를 참고했습니다.
네트워크 플로우 알고리즘을 미리 알고 있어야 풀 수 있습니다.

전체코드

import sys
from collections import deque

input = sys.stdin.readline
N, P = map(int, input().split())

MAX = 401
c = [[0] * MAX for _ in range(MAX)]
f = [[0] * MAX for _ in range(MAX)]
graph = [[] for _ in range(MAX)]

def network_flow(start, end):
    max_flow = 0
    while True:
        visit = [-1] * MAX
        q = deque([start])
        
        while q:
            x = q.popleft()
            for y in graph[x]:
                if c[x][y] - f[x][y] > 0 and visit[y] == -1:
                    q.append(y)
                    visit[y] = x
                    if y == end:
                        break

        if visit[end] == -1:
            break

        flow = float('inf')
        
        i = end
        while i != start:
            flow = min(flow, c[visit[i]][i] - f[visit[i]][i])
            i = visit[i]

        i = end
        while i != start:
            f[visit[i]][i] += flow
            f[i][visit[i]] -= flow
            i = visit[i]

        max_flow += flow

    return max_flow

for _ in range(P):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    c[a][b] = 1

print(network_flow(1, 2))