[Java] 백준 1671번 상어의 저녁식사

이분매칭 문제입니다.

열혈강호2와 유사한 문제입니다.
https://j3sung.tistory.com/1019

[Java] 백준 11376번 열혈강호2

상어가 속도, 사이즈, 지능이 주어질 때 다른 상어의 속도, 사이즈, 지능이 전부 같거나 작을 때 먹을 수 있습니다.
최대 2마리 까지 먹을 수 있으며 서로 먹고 먹힐 수는 없습니다.

이분매칭을 사용해서 상어들을 매칭해줍니다.
매칭 할 때 eat함수를 사용해서 해당 상어를 먹을 수 있는지 확인합니다.
먹을 수 있으면 해당 상어를 점유(먹으려고 한 상어가 있는지)한 상어가 있는지 확인합니다.
점유한 상어가 다른 상어를 먹을 수 있는지 (양보가 가능한지) 확인하고 가능하면 해당 상어를 점유합니다.
위의 과정을 반복해서 문제를 해결하였습니다.

유의해야하는 사항으로는 서로 먹고 먹힐 수 없으므로, 먹고 먹히는 경우는 3개의 능력치가 같은 경우입니다.
1번 상어 : 1 1 1
2번 상어 : 1 1 1
3번 상어 : 1 1 1
위의 경우 세마리의 상어가 서로 먹고 먹힐 수 있습니다.
이를 방지해주기 위해서 능력치가 같을 경우 인덱스를 비교해서 인덱스가 큰 상어만 작은 상어를 먹을 수 있도록 해주었습니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
	static int ans;
	static int n;
	static int visitCnt;
	static Data[] sharks;
	static int visit[];
	static int eat[];

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());

		ans = 0;
		n = Integer.parseInt(st.nextToken());
		sharks = new Data[n + 1];
		visit = new int[n + 1];
		eat = new int[n + 1];

		for (int i = 1; i <= n; ++i) {
			st = new StringTokenizer(br.readLine());
			int size = Integer.parseInt(st.nextToken());
			int speed = Integer.parseInt(st.nextToken());
			int brain = Integer.parseInt(st.nextToken());
			sharks[i] = new Data(size, speed, brain);
		}

		for (int i = 1; i <= n; ++i) {
			++visitCnt;
			if (DFS(i) == 1) {
				++ans;
			}
			++visitCnt;
			if (DFS(i) == 1) {
				++ans;
			}
		}

		bw.write(n - ans + "\n");
		bw.close();
	}

	public static int DFS(int loc) {
		if (visit[loc] == visitCnt) {
			return 0;
		}
		visit[loc] = visitCnt;

		for (int i = 1; i <= n; ++i) {
			if (loc == i) {
				continue;
			}

			if (eat(loc, i)) {
				if (eat[i] == 0 || DFS(eat[i]) == 1) {
					eat[i] = loc;
					return 1;
				}
			}
		}

		return 0;
	}

	public static boolean eat(int a, int b) {
		if (sharks[a].size == sharks[b].size && sharks[a].speed == sharks[b].speed && sharks[a].brain == sharks[b].brain
				&& a < b) {
			return false;
		}

		if (sharks[a].size >= sharks[b].size && sharks[a].speed >= sharks[b].speed && sharks[a].brain >= sharks[b].brain) {
			return true;
		}

		return false;
	}

	public static class Data {
		int size;
		int speed;
		int brain;

		public Data(int size, int speed, int brain) {
			this.size = size;
			this.speed = speed;
			this.brain = brain;
		}
	}
}