도시 왕복하기 1

🤔 접근

문제를 읽고 최대유량 알고리즘이 필요하겠구나 생각이 들었다. 경로가 겹치면 안 되기 때문에 양의 방향의 모든 간선의 용량을 1로 설정하면 될 것이라고 생각했다.

💻 코드

# 17412
import sys
input = sys.stdin.readline
from collections import deque

# n개의 정점과 p개의 간선
n, p = map(int, input().split())
graph = [[] for _ in range(n+1)]

# capacity, flow
capacity = [[0] * (n+1) for _ in range(n+1)]
flow = [[0] * (n+1) for _ in range(n+1)]

# graph update u -> v
for _ in range(p):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u) # 음수 유량 고려
    capacity[u][v] = 1 # 경로 겹치면 안 되므로 1


def bfs_path(source, sink, visited): # source부터 sink까지 흘릴 수 있는 추가 유량이 있는지, 있다면 그 경로를 visited에 저장
    q = deque()
    q.append(source)
    while q and visited[sink] == -1: # 갈 곳이 남아있고, 아직 도착점에 도달 안했다면 반복
        u = q.popleft()
        for v in graph[u]: # 역방향을 포함하여 연결된 다음 정점 모두 순회
            leftover_flow = capacity[u][v] - flow[u][v]
            if visited[v] == -1 and leftover_flow > 0: # 방문한 적 없고, 잔여용량 남아 있으면 방문
                q.append(v)
                visited[v] = u # 어디서 왔는지 기록
                if v == sink: # sink에 도착했다면 종료
                    break

    if visited[sink] == -1: # 경로가 없다는 뜻
        return False
    
    return True

def edmonds_karp(source, sink):
    ans = 0
    while True: # 업데이트할 유량이 있으면 반복, 즉 bfs 결과에 따라 결정
        visited = [-1] * (n+1)
        if not bfs_path(source, sink, visited): # path 가 없다면 업데이트 종료
            break
     
        j = sink
        while j != source:
            i = visited[j]
            flow[i][j] += 1
            flow[j][i] -= 1
            j = i

        ans += 1
    return ans


print(edmonds_karp(1,2))

🖋️ 에드몬드 카프 알고리즘 정리

핵심은 모든 경로에 대해 더이상의 추가 유량이 흐르지 않을 때까지 경로를 찾고 업데이트 시키는 것이다.
음수 유량을 포함한 경로도 다 확인해야한다. 이때, 최대 유량 알고리즘에서 경로를 확인하는 방식이 BFS이면 에드몬드 카프 알고리즘이고, DFS면 포드 풀커슨 알고리즘인 것이다.

크게 두 가지 함수를 이용하여 구현하였다.

1. BFS
   source부터 sink까지 흐를 수 있는 추가 유량이 있는지 그 경로를 찾고 경로를 visited 리스트에 기록해두는 함수
2. edmonds_karp
   bfs로 경로를 찾고 아직 가능한 경로가 있다면 다음 두 가지를 실행한다.

• min_flow를 찾는 로직
• 찾은 min_flow를 flow에 업데이트 시키는 로직

나동빈님의 설명이 이해하는데 많은 도움이 되었다.
https://youtu.be/Wn51_ypG_T8?si=2rgPCUF5SlmiG8UE

note (edmonds_karp)

#### 에드몬드카프 알고리즘
# graph, capacity, flow
graph = [[] for _ in range(n+1)]
capacity = [[0] * (n+1) for _ in range(n+1)]
flow = [[0] * (n+1) for _ in range(n+1)]

# graph update u -> v
for _ in range(p):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u) # 음수 유량 고려
    capacity[u][v] = 

def bfs_path(source, sink, visited): # source부터 sink까지 흘릴 수 있는 추가 유량이 있는지, 있다면 그 경로를 visited에 저장
    q = deque()
    q.append(source)
    while q and visited[sink] == -1: # 갈 곳이 남아있고, 아직 도착점에 도달 안했다면 반복
        u = q.popleft()
        for v in graph[u]: # 역방향을 포함하여 연결된 다음 정점 모두 순회
            leftover_flow = capacity[u][v] - flow[u][v]
            if visited[v] == -1 and leftover_flow > 0: # 방문한 적 없고, 잔여용량 남아 있으면 방문
                q.append(v)
                visited[v] = u # 어디서 왔는지 기록
                if v == sink: # sink에 도착했다면 종료
                    break

    if visited[sink] == -1: # 경로가 없다는 뜻
        return False
    
    return True

def edmonds_karp(source, sink):
    ans = 0
    while True: # 업데이트할 유량이 있으면 반복, 즉 bfs 결과에 따라 결정
        visited = [-1] * (n+1)
        if not bfs_path(source, sink, visited): # path 가 없다면 업데이트 종료
            break
        
        ## min_flow 찾는 과정
        min_flow = 1e9
        j = sink
        while j != source:
            i = visited[j]
            leftover_flow = capacity[i][j] - flow[i][j]
            min_flow = min(min_flow, leftover_flow)
            j = i
        
        # 위에서 찾은 min_flow를 flow에 업데이트
        j = sink
        while j != source:
            i = visited[j]
            flow[i][j] += 1
            flow[j][i] -= 1
            j = i

        ans += min_flow

    return ans