반응형 최대유량1 백준 #1671 상어의 저녁식사(최대 유량) 이번 문제에 대한 알고리즘 힌트에는 이분 매칭으로 되어 있지만, 저는 최대 유량으로 풀었습니다. 상어 A 와 상어 B를 비교해서 상어 A의 조건이 상어 B보다 좋거나 같다면, 상어 A는 상어 B로 가는 간선이 있다고 선언합니다. 이렇게 하면 유향 그래프가 만들어집니다. 그런데, 상어 한마리당 오직 두마리만 먹을 수 있기 때문에 그에 대한 제한을 하면 됩니다. 최대 유량을 구하는 방법은, 상어 A가 먹을 수 있는 상어에 대해서 식사를 합니다. 두번의 식사가 가능하면 그만큼 상어의 수는 줄어듭니다. 그런데, 그 상어중 이미 다른 상어에게 먹힌 상어가 있을 수 있습니다. 그런 경우, 해당 상어를 먹은 다른 상어가 또 다른 상어를 먹을 수 있는지 검사합니다. 다른 상어를 먹을 수 없다면, 그 상어는 넘어가고 다.. 2022. 9. 27. 이전 1 다음 728x90
