[백준/JAVA] 1671 상어의 저녁식사

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

1671번: 상어의 저녁식사

 

문제설명

상어가 동족을 잡아 먹으며 몇마리가 살 수 있는지에 대해 묻는 문제

 

 

문제풀이

각 상어가 잡아먹을 수 있는 상어를 가르키는 인접리스트 형태로 구현한 후 이분 매칭을 통해 문제를 풀어내면 된다.

 

1. 크기, 속도, 지능 셋 다 커야 잡아 먹을 수 있음

2. 한 상어가 최대 두마리 까지 먹을 수 있음

3. a상어가 b상어를 먹은 상태라면 b상어는 a상어를 먹을 수 없음

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Objects;
import java.util.StringTokenizer;

public class P1671 {
	static int n;
	static Triple[] shark;
	static boolean[] visited;
	static int[] bmatch;
	static List<Integer>[] adjList;

	static void init() throws IOException {
		n = rn();
		shark = new Triple[n];

		for (int i = 0; i < n; ++i) shark[i] = new Triple(rstn(),rstn(),rstn());

		bmatch = new int[n + 1];
		Arrays.fill(bmatch, -1);

		adjList = new ArrayList[n];
		for (int i = 0; i < n; ++i) adjList[i] = new ArrayList<>();

		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				if (i == j) continue;
				if (shark[i].compare(shark[j])) {
					if (shark[i].equals(shark[j])&& i > j) continue;
					adjList[i].add(j);
				}
			}
		}
	}

	static boolean dfs(int a) {
		for (int i = 0; i < adjList[a].size(); ++i) {
			int b = adjList[a].get(i);
			if (visited[b]) continue;
			visited[b] = true;
			if (bmatch[b] == -1 || dfs(bmatch[b])) {
				bmatch[b] = a;
				return true;
			}
		}
		return false;
	}

	public static void main(String[] args) throws IOException {
		br = Source.getBufferedReader();
		init();

		int answer = 0;
		for (int i = 0; i < n; ++i) {
			visited = new boolean[n];
			answer += dfs(i) ? 1 : 0;
			visited = new boolean[n];
			answer += dfs(i) ? 1 : 0;
		}

		System.out.println(n - answer);

	}
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int rn() throws IOException {return Integer.parseInt(br.readLine());}
	static void est() throws IOException {st = new StringTokenizer(br.readLine());}
	static int rstn() throws IOException {if(st==null||!st.hasMoreTokens()) est(); return Integer.parseInt(st.nextToken());}
	static class Triple{
		int x,y,z;public Triple(int x, int y,int z) {this.x = x;this.y = y;this.z = z;}
		boolean compare(Triple o) {return this.x >= o.x && this.y >= o.y && this.z >= o.z;}
		@Override
		public boolean equals(Object o) {
			Triple triple = (Triple) o;
			return x == triple.x && y == triple.y && z == triple.z;
		}
		@Override
		public int hashCode() {
			return Objects.hash(x, y, z);
		}
	}
}