https://www.acmicpc.net/problem/11376최대 유량 (Max Flow) 의 특수한 형태인 문제들은 기존의 O(V * E^2)의 시간복잡도 대신 이분 매칭이라는 또다른 알고리즘을 통해 O(VE)의 시간으로 해결할 수 있다. 이번 문제 같은 경우가 딱 그런 경우인데, #11375번 열혈강호 문제의 업그레이드 버전이라 볼 수 있다. 사실 업그레이드도 아닌 것이,,, 그냥 한 정점에 대해 DFS와 visited 배열 초기화를 두번씩 돌려주면 된다.다음 그림은 문제에서 주어진 입력값에 대한 이분 매칭 그래프를 그려본 것이다. 일할 사람을 1~5의 숫자로, 해야하는 일을 편의상 A~E까지의 알파벳으로 나타냈다. 또한 visited배열은 각 일에 대한 방문 여부, matched 배열은 해당 ..
