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

#1671 상어의 저녁식사

난이도 : 플레 3

유형 : 이분 매칭

1671번: 상어의 저녁식사

▸ 문제

어떤 상어는 저녁식사로 서로를 먹는다. 모든 상어는 자신과 다른 상어의 크기, 속도, 지능을 수치로 나타낸 것을 알고 있다. 만약, 상어 A의 크기, 속도, 지능이 상어 B의 크기, 속도, 지능보다 크거나 같다면 상어 A는 상어 B를 먹을 수 있다. 그러나, 상어들의 왕 김재홍은 상어들이 많이 없어지는 것을 방지하기 위해서 한 상어가 최대 두 개의 상어만 먹을 수 있게 했다. 상어들은 김재홍의 말을 모두 듣는다.

한 상어가 다른 상어를 잡아먹는 동안 나머지 상어들은 상어를 잡아먹을 수 없으며, 이미 잡아먹힌 상어는 다른 상어들을 잡아먹을 수 없다.

N마리 상어의 크기, 속도, 지능이 주어졌을 때, 살아남을 수 있는 상어 수의 최솟값을 구하시오.

▸ 입력

첫째 줄에 상어의 마리 수 N이 주어진다. 이 값은 50보다 작거나 같은 자연수이다. 둘째 줄부터 각 상어의 크기, 속도, 지능의 정보가 주어진다. 이 값은 2,000,000,000보다 작거나 같은 자연수이다.

▸ 출력

첫째 줄에 살아남을 수 있는 상어 수의 최솟값을 출력한다.

 

문제 풀이  

이분 매칭 문제로 어떤 상어가 어떤 상어를 먹을 수 있는지에 대한 관계도 그래프를 먼저 그려줘야 한다. 세 가지 특성(크기, 속도, 지능)을 모두 고려해줘야 한다. 만약 특성이 모두 같을 경우 서로가 먹을 수 있기 때문에 중복이 발생한다. 그래서 인덱스와 같은 지표로 우선순위를 정해줘서 단방향으로 설정해줘야 한다. 

 

따라서 (a, b) 그래프 간선이 성립되는 경우는

• a가 b보다 세 가지 특성이 모두 높을 때
•  혹은 a와 b의 세 가지 특성이 모두 같은데, b의 인덱스 가 더 높을 때이다.

 

예제 1번의 상어 포식자 관계를 초기화하면 다음과 같다.  이렇게 네트워크 플로우를 만들어준 다음 각 한 마리 상어 당 2번씩 매칭을 시도해주면 된다. 

 

상어 매칭

 

 

이분매칭에 대한 자세한 내용은 여기를 참고해주세요.

 

 

 

풀이 코드 

import java.io.*;
import java.util.*;

public class Main {
	static class Shark{
		int size;
		int speed;
		int intelligence;
		
		public Shark(int size, int speed, int intelligence) {
			this.size = size;
			this.speed = speed;
			this.intelligence = intelligence;
		}

	}

	static int n;
	static List<Integer>[] list;
	static int[] eat;
	static boolean[] check;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		
		StringTokenizer st;
		Shark[] sharks = new Shark[n+1];
		list = new ArrayList[n+1];
		for(int i=1; i<=n; i++) {
			st = new StringTokenizer(br.readLine());
			sharks[i] = new Shark(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
			list[i] = new ArrayList<>();
		}
		
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=n; j++) {
				int cond = compareShark(sharks[i],sharks[j]);
				if(cond == 1 || (cond == 2 && i<j)) list[i].add(j);
			} 
		}
		
		eat = new int[n+1];
		check = new boolean[n+1];
		int cnt = 0;
		
		for(int i=1; i<=n; i++) {
			for(int j=0; j<2; j++) {
				Arrays.fill(check, false);
				if(dfs(i))cnt++;	
			}
		}
		System.out.println(n-cnt);
	}
    
	static int compareShark(Shark s1, Shark s2) {
		int cnt = 0;
		if(s1.size < s2.size) return 0;
		if(s1.size == s2.size)  cnt++;
		if(s1.speed < s2.speed) return 0;
		if(s1.speed == s2.speed)  cnt++;
		if(s1.intelligence < s2.intelligence) return 0;
		if(s1.intelligence == s2.intelligence)  cnt++;
		if(cnt == 3) return 2;
		return 1;
	}
	
	static boolean dfs(int here) {
		for(int nxt : list[here]) {
			if(check[nxt]) continue;
			check[nxt] = true;
			
			if(eat[nxt] == 0 || dfs(eat[nxt])) {
				eat[nxt] = here;
				return true;
			}
		}
		return false;
	}
}