백준 #1671 상어의 저녁식사(최대 유량)

이번 문제에 대한 알고리즘 힌트에는 이분 매칭으로 되어 있지만, 저는 최대 유량으로 풀었습니다.

 

상어 A 와 상어 B를 비교해서 상어 A의 조건이 상어 B보다 좋거나 같다면, 상어 A는 상어 B로 가는 간선이 있다고 선언합니다.  이렇게 하면 유향 그래프가 만들어집니다.  그런데, 상어 한마리당 오직 두마리만 먹을 수 있기 때문에 그에 대한 제한을 하면 됩니다.

 

shark's dinner

 

최대 유량을 구하는 방법은,

 

상어 A가 먹을 수 있는 상어에 대해서 식사를 합니다.  두번의 식사가 가능하면 그만큼 상어의 수는 줄어듭니다.

그런데, 그 상어중 이미 다른 상어에게 먹힌 상어가 있을 수 있습니다.  그런 경우, 해당 상어를 먹은 다른 상어가 또 다른 상어를 먹을 수 있는지 검사합니다.  다른 상어를 먹을 수 없다면, 그 상어는 넘어가고 다시 다른 상어를 검사합니다.

 

이런 절차를 반복하면 최대로 먹힐 수 있는 상어의 수를 구하게 됩니다.

 

다음과 같이 5마리의 상어가 있다고 한다면, 인접리스트를 구하면 다음 표와 같습니다.

#	크기	속도	지능	인접리스ㅌ
1	4	5	5
2	10	10	8	1, 4, 5
3	5	7	10	1
4	8	7	7	1
5	8	10	3

 

1번 상어는 먹을 수 있는 상어가 없습니다.

2번 상어는 1번과 4번을 먼저 먹겠죠.

3번 상어는 1번을 먹으려고 하는데, 1번은 이미 2번이 차지했습니다.  2번 상어는 새로운 상어를 찾고, 5번을 먹습니다.  그리고 1번은 3번 상어가 차지합니다.

4번 상어는 1번을 먹으려고 하는데, 3번이 차지했습니다.  3번은 더이상 먹을 수 있는 상어가 없기 때문에 4번 상어는 한마리도 먹을 수 없습니다.

5번은 인접리스트가 비어있기때문에 넘어갑니다.

 

그래서 최종적으로 3마리의 상어를 먹을 수 있습니다.  남은 상어는 2마리가 되겠죠.

 

그리고 이 문제에서 주의할 점은 같은 능력치의 상어가 여러마리가 있는 경우입니다.  예를 들어서 위 문제에서 4번 상어가 1번 상어를 먹고, 2번 상어가 4번 상어와 5번 상어를 먹을 수 있습니다.  이렇게 능력치가 서로 다르면 선후관계로 먹을 수 있습니다.  하지만 능력치가 같은 상어의 경우에는 안 됩니다.

 

예를 들어서 예제 입력 4와 같은 경우에는 능력치가 모두 같은 경우입니다.  이런 경우에는 사이클을 돌 수 있기 때문에, 그에 대한 조치가 필요합니다.  제 경우에는 별도의 플래그를 두어서 먹고 먹히는 관계의 경우에는 먹지 못 하도록 하였습니다.