개발일지

개념 유량이 있는 그래프에서 얼마나 많은 유량을 보낼 수 있는지 확인하는 알고리즘 유량(Flow) : 두 정점 사이에서 흐르는 유량 용량(Capacity) : 두 정점 사이에서 최대로 흐를 수 있는 유량 소스(Source) : 유량이 시작되는 정점 싱크(Sink) : 유량이 도착하는 정점 용량 제한 속성 (Flow 유량은 용량을 넘을 수 없다. 유량의 대칭성 A -> B로 10이 흘렀으면, B -> A로 다시 10을 보낼 수 있다. => 유량을 보낼 경로를 찾을 때 보통 BFS를 사용하고 BFS는 우선순위를 고려하지 않고 경로를 찾게 된다. 이럴 때 최대로 흐르는 경로가 아닌 다른 경로를 선택하는 문제를 해결할 때 필요한 개념이다. 작동원리 1. 유량 그래프를 모델링한다 => 역방향 간선도 필수적으로 추..