1671번 상어의 저녁식사

이분 매칭 문제이다.

1. 상어 1의 3가지와 상어 2의 3가지가 같을 때, 잘 처리해야 한다.

2. 각각 2마리씩 먹을 수 있으므로, DFS를 2번 돌린다.

3. 2번 돌릴 때에, 그 사이에 visit를 한 번 더 초기화 해줘야한다.(http://donggod.tistory.com/51 참고)

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

#include <iostream>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
 
using namespace std;
 
#define MAX 50
 
typedef struct shark
{
    int size;
    int speed;
    int intellect;
}shark;
 
shark s[MAX];
 
int Connection[MAX][MAX] = { 0, };
 
int A[MAX] = { 0, }; // 잡아 먹는 집단
int B[MAX] = { 0, }; // 잡아 먹히는 집단
 
int N = 0;
 
int visit[MAX] = { 0, };
 
int DFS(int start)
{
    if (visit[start] == 1) return -1;
 
    visit[start] = 1; // 누락 조심. 방문 표시를 안 해줘서 왜 안 되는지 계속 생각하였다.
 
    for (int i = 0; i < N; i++)
    {
        if (Connection[start][i] == 1) // start가 i를 잡아 먹을 수 있을 때
        {    
            if (B[i] == -1 || DFS(B[i]) == 1)
            {
                // i가 누군가에 의해 잡아 먹히지 않았을 때 (B[i] == 1) 또는 
                // 누군가가 i를 잡아 먹을 수 있을 때 (DFS(B[i]) == 1)
 
                A[start] = i; // start는 i를 잡아 먹을 수 있다.
                B[i] = start; // i는 start에 의해 잡아 먹힌다.
 
                return 1;
            }
        }
    }
 
    return -1;
}
 
void BipartiteMatching()
{
    memset(A, -1, sizeof(A));
    memset(B, -1, sizeof(B));
 
    int ret = 0;
 
    for (int i = 0; i < N; i++)
    {
        memset(visit, -1, sizeof(visit));
 
        DFS(i);
 
        memset(visit, -1, sizeof(visit)); 
        // 여기서 visit 방문 표시를 초기화 해줘야한다.
 
        DFS(i);
    }
}
 
int main(void)
{
    int Size = 0, Speed = 0, Intellect = 0;
 
    memset(Connection, -1, sizeof(Connection));
 
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++)
    {
        scanf("%d %d %d", &Size, &Speed, &Intellect);
 
        s[i].size = Size;
        s[i].speed = Speed;
        s[i].intellect = Intellect;
    }
    
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (i == j) continue; // 같으면 무시
 
            if (s[i].size == s[j].size && s[i].speed == s[j].speed && s[i].intellect == s[j].intellect && i > j) continue;
            // 같을 경우, A가 B를 잡아 먹을 수 있는데, 이 때문에 아래에서 또 B가 A를 잡아 먹는 이상한 상황이 발생한다.
 
            // 상어 1 vs 상어 2 (예시)
            // 이렇게 되면 같을 경우, i(1)를 처리 할 때는 i(1) < j(2) 일 때 먹을 수 있고, 
            // i(2)를 처리할 때는 j가 1이기 때문에 i > j 조건에 성립되어 continue 되어버린다.
 
            if (s[i].size >= s[j].size && s[i].speed >= s[j].speed && s[i].intellect >= s[j].intellect)
            {
                Connection[i][j] = 1;
            }
        }
    }
 
    BipartiteMatching();
 
    int live = 0;
 
    for (int i = 0; i < N; i++)
    {
        if (B[i] == -1) ++live;
    }
 
    printf("%d\n", live);
 
    return 0;
}