[백준] #6096번 Max Flow python

 

Network flow 문항을 찾다가 Max flow문제를 발견하였다.

 

https://www.acmicpc.net/problem/6086

6086번: 최대 유량

 

 

시간 복잡도 : O(VE^2)

 

정점 중 Capacity가 주어진 파이프 그래프가 주어졌을 때, 정점 start_node에서 정점 end_node까지의 최대 flow를 출력하는 문제이다.

 

Edmonds_Karp Algorithm을 적용하여 풀이하였다.

 

코드를 조금씩 살펴보도록 하자.

import sys
from collections import deque

totalFlow = 0
MAX_V = 100
INF = sys.maxsize

N = 6
capacity = [[0] * (N + 1) for _ in range(N + 1)]
flow = [[0] * (N + 1) for _ in range(N + 1)]
flowList = [[] for _ in range(N + 1)]
flowdict = {}

start_node = 1
# start one
end_node = 6
# end one

input_num = int(sys.stdin.readline())
for _ in range(input_num) :
    S, T, c = map(int, sys.stdin.readline().split())
    capacity[S][T] = int(c)
    # capacity[dv][sv] = int(c)
    # flowList[S].append(T)
    # flowList[T].append(S)
    if S not in flowdict:
        flowdict[S] = [T]
    else:
        flowdict[S].append(T)
    if T not in flowdict:
        flowdict[T] = [S]
    else:
        flowdict[T].append(S)

위와 같이 입력을 받아준다.

 

다음과 같은 dataset을 갖는다.

 

variable

• totalFlow : 총 유량
• MAX_V : 100
• INF : sys.maxsize
• N : 총 node의 수
• capacity : 용량
• flow : 유량
• flowdict : dictionary for nodes
• start_node : 시작 노드
• end_node : 끝 노드
• input_num : 간선의 개수
• S, T, c : 노드1(S) -> 노드2(T) 에서 capacity인 c 

정수인 입력 값을 다음과 같이 받는다고 합시다.

 

10
1 2 12
1 4 11
2 3 6
2 4 3
2 5 5
2 6 9
3 6 8
4 5 9
5 3 3
5 6 4

 

그럼 flowdict은 다음과 같이 나옵니다.

 

{1: [2, 4], 2: [1, 3, 4, 5, 6], 4: [1, 2, 5], 3: [2, 6, 5], 5: [2, 4, 3, 6], 6: [2, 3, 5]}

 

이와 같이 모든 방향의 간선들을 구할 수 있습니다.

 

그렇다면,

def fromCtoI(target_node):
    if target_node.isupper():
        return ord(target_node) - ord('A')
    else:
        return ord(target_node) - ord('a') + 26

위 코드를 보면,

 

fromCtoI 함수에서 target_node를 parameter로 받아 Upper인 경우와 Lower인 경우로 나눕니다.

 

• Upper

upper의 경우에는 ord 내장함수를 사용하여 Char의 값을 Integer로 바꿉니다.

• Lower

lower의 경우에는 ord 내장함수를 사용하여 Char의 값을 Integer로 바꿉니다.

 

한편, ord('a') == 97이고 ord("A") == 65 입니다.

 

이 경우, 26개의 알파벳 다음에 오므로 26을 더해줍니다.

 

edmonds_Karp와 BFS코드는 아래와 같습니다.

def edmonds_Karp(start_node, end_node):
    while 1:
        visit = [-1 for i in range(MAX_V)]
        if BFS(start_node, end_node, visit):
            break

        minFlow = INF

        i = end_node
        while i != start_node:
            minFlow = min(minFlow, capacity[visit[i]][i] - flow[visit[i]][i])
            i = visit[i]

        i = end_node
        while i != start_node:
            flow[visit[i]][i] += minFlow
            flow[i][visit[i]] -= minFlow
            i = visit[i]

        global totalFlow
        totalFlow += minFlow

    return totalFlow

 

def BFS(start_node, end_node, visit):
    dq = deque()
    dq.append(start_node)

    while dq and visit[end_node] == -1:
        S = dq.popleft()

        for T in flowdict[S]:
            if capacity[S][T] - flow[S][T] > 0 and visit[T] == -1:
                dq.append(T)
                visit[T] = S

                if T == end_node:
                    break

    if visit[end_node] == -1:
        return True
    else:
        return False

 

 

 

 

 

 

 

edmons karp algorithm을 사용하여 최대 유량을 구하는 문제를 풀었다.

 

NewWork Flow문항은 처음 접해보는 것이라 익숙치 않았다.

 

읽어주셔서 감사드립니다.

 

이론은 아래 블로그를 참고하시기 바랍니다.

https://janghan-kor.tistory.com/54

NetWork Flow Algorithm (네트워크 플로우)

출처:https://hellominchan.tistory.com/354