BOJ 백준 1671 상어의 저녁식사

 

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

 

[ 문제 요약 ]

• 상어의 크기, 속도, 지능이 주어지며, A 상어가 B 상어 보다 크기 속도 지능이 모두 크거나 같다면 A 상어는 B 상어를 잡아먹을 수 있습니다.
• 한 상어는 최대 두 개의 상어만 먹을 수 있고, 이미 잡아먹힌 상어는 다른 상어를 먹을 수 없으며, 한 상어가 다른 상어를 잡아먹을 동안 다른 상어들은 가만히 있습니다.
• N 마리 상어 크기, 속도, 지능이 주어질 때, 살아남을 수 있는 상어 수의 최솟값을 출력합니다.

 

[ 테스트 케이스 설명 ]

5		// 상어의 마리수 (1<=50)
4 5 5		// 크기(1<=20억), 속도(1<=20억), 지능(1<=20억)
10 10 8
5 7 10
8 7 7
8 10 3
//살아남을 수 있는 상어 수의 최솟값 : 2

 

 

[ 알고리즘 분류 ]

• 이분 매칭

 

[ 문제 해설 ]

한 상어당 2마리를 잡을 수 있고, 또한 잡아먹힌 상어는 자기를 잡아먹은 상어를 잡을 수 없다는 조건이 있습니다.

이를 토대로 간선을 양방향이 아니라 단방향으로 잡아 줍니다.

단, 능력치가 같은 경우는 서로를 잡아먹을 수 있어서 둘 중 하나만 잡아먹을 수 있게 처리해 주어야 합니다.

능력치가 같은 경우 인덱스가 작은 쪽이 큰 쪽을 잡을 수 있도록 간선을 매칭 시켜 주면 됩니다.

그 후 이분 매칭을 2번씩 돌려주면 됩니다.

이분 매칭 구현 시 무한 루프 방지를 위해 방문 표현을 boolean 배열을 선언해 매 dfs마다 초기화하는데, 이렇게 하는 것보다 int형 배열을 선언하여 방문 시간으로 관리하는 것이 공간 복잡도와 시간 복잡 도면에서 유리합니다.

디테일은 코드를 통해 확인 가능합니다.

 

[ 정답 코드 ]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
class Main{

	static int time;
	static int N;
	static int match[];
	static int visitTime[];
	static List<Shark> shark;
	static List<Integer> adList[];
	
	public static void main(String[] args)throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());// 상어의 마리수 (1<=50)
		match = new int[N + 1];
		visitTime = new int[N + 1];
		shark = new ArrayList<>();
		adList = new ArrayList[N + 1];
		
		for(int i=1; i<=N; i++)
		{
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());// 크기(1<=20억)
			int b = Integer.parseInt(st.nextToken());// 속도(1<=20억)
			int c = Integer.parseInt(st.nextToken());// 지능(1<=20억)
			shark.add(new Shark(a,b,c));
			adList[i] = new ArrayList<>();
		}
		
		for(int i=1; i<=N; i++)
		{
			Shark s1 = shark.get(i - 1);
			for(int j=1; j<=N; j++)
			{
				if(i == j)
					continue;
				
				Shark s2 = shark.get(j - 1);
				if(s1.a == s2.a && s1.b == s2.b && s1.c == s2.c)
				{
					if(i < j)
						adList[i].add(j);
				}
				else if(s1.a >= s2.a && s1.b >= s2.b && s1.c >= s2.c)
					adList[i].add(j);
			}
		}
				
		int cnt = N;
		
		for(int i=1; i<=N; i++)
		{
			++time;
			if(dfs(i)) --cnt;
			++time;
			if(dfs(i)) --cnt;
		}
		System.out.print(cnt);
	}
	static boolean dfs(int now) {
		for(int next : adList[now])
		{
			if(visitTime[next] == time)
				continue;
			
			visitTime[next] = time;
			
			if(match[next] == 0 || dfs(match[next]))
			{
				match[next] = now;
				return true;
			}
		}
		return false;
	}
	static class Shark{
		int a, b, c;
		Shark(int a, int b, int c){
			this.a=a;
			this.b=b;
			this.c=c;
		}
	}
}