[BOJ] 백준 1298번 노트북의 주인을 찾아서 (Java)

#1298 노트북의 주인을 찾아서

난이도 : 플레 5

유형 : 이분 매칭 

1298번: 노트북의 주인을 찾아서

▸ 문제

어느 날 모든 학생들은 한 명이 한개의 노트북을 가지고 공부하던 도중, 자리를 바꾸다가 그만 노트북이 뒤섞이고 말았다. 대다수의 학생들은 자신의 노트북을 잘 알고 있어서 자신의 노트북을 받을 수 있었지만, 애석하게도 N명의 학생들이 정확히 자신의 노트북이 어떤것인지 알지 못했다. 왜냐하면 그들은 노트북을 구입한게 바로 어제였기 때문이다.

어차피 새것인 노트북, 바뀐들 어떠하랴.

그들에게 자신의 노트북이라고 생각되는 노트북들을 얘기해 보라고 했다.

이번에는 정말 신기하게도 그들 각각이 노트북을 여러개 선택한 것이었다! “이것 아니면 이것 아니면 이것 아니면 이것 일거 같아요”라카더라.

우리의 목적은 이들의 요구를 가장 많이 만족시키는 것이다.

요컨대, 자신이 자신의 것 같다라고 얘기한 노트북을 갖는 사람을 최대화 하라는 소리다.

▸ 입력

첫째 줄에는 노트북이 섞인 날 어제 노트북을 구입한 사람의 수 N(1 ≤ N ≤ 100)과 노트북 예상의 개수 M(0 ≤ M ≤ 5,000) 주어진다.

둘쨋줄에서 M+1번째 줄 까지는 각각 한 줄마다 a b가 주어지는데, 이는 a번 사람이 b번 노트북을 자신의 것이라고 생각한다는 의미를 갖는다.

노트북과 사람의 번호는 1보다 크거나 같고, N보다 작거나 같다. 두 사람 또는 두 노트북이 같은 번호를 갖는 경우는 없다.

▸ 출력

최대로 만족될 수 있는 사람 수를 출력한다.

 

문제 풀이  

네트워크 플로우와 연계되는 개념인 이분 매칭(Bipartite Matching) 알고리즘 문제이다. 이분 매칭은 이분 그래프에서 최대 매칭을 찾는 문제를 간단하게 이분 매칭이라고 부른다.

• 그룹 A(사람)와 그룹 B(노트북)를 주어진 대로 연결하고 용량을 1로 하면 해당 그래프의 최대 유량을 구한 뒤 유량이 흐르는 간선을 모으면 최대 매칭이 된다.

 

예제 1번은 모두 1대1 매칭이 되기 떄문에 만족되는 사람의 수는 당연히 N(5)가 된다.예제 2번은 이분 매칭을 시켜줬을 때 어떻게 매칭이 되는지 살펴보자.

 

1번 노트북 2와 매칭

• 1번은 가장 숫자가 낮은 노트북2와 매칭된다.

1번 노트북2와 매칭

 

2번 노트북 2와 매칭, 1번 노트북 3과 매칭

• 2번 또한 가장 낮은 번호 노트북 2와 매칭된다.
• 기존에 이미 매칭되어있던 1번은 노트북 3과도 매칭이 가능하므로 노트북 3과 매칭된다.

2번 노트북 2와 매칭, 1번 노트북 3과 매칭

 

3번 노트북 1과 매칭, 4번 노트북 매칭 x

• 노트북 2,3번은 이미 매칭되어있으므로 3번은 노트북 1과 매칭된다.
• 4번은 매칭 가능한 노트북이 없다.

3번 노트북 1과 매칭, 4번 노트북 매칭 x

 

5번 노트북 4와 매칭

• 5번은 모든 노트북과 매칭이 가능하므로 남은 노트북과 매칭해주면 된다. 따라서, 총 4명이 만족할 수 있다.

5번 노트북 4와 매칭

 

풀이 코드 

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

public class Main {

	static List<Integer>[] list;
	static int[] task;
	static boolean[] check;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		list = new ArrayList[n+1];
		for(int i=1; i<=n; i++) {
			list[i] = new ArrayList<>();
		}
		
		task = new int[n+1];
		check = new boolean[n+1];
		for(int i=0; i<m; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			list[a].add(b);
		}
		
		int cnt = 0;
		for(int i=1; i<=n; i++) {
			Arrays.fill(check, false);
			if(dfs(i)) cnt++; 
		}
		
		System.out.println(cnt);
	}
	
	static boolean dfs(int here) {
		for(int nxt : list[here]) {
			if(check[nxt]) continue;
			check[nxt] = true;
			
			if(task[nxt] == 0  || dfs(task[nxt])) {
				task[nxt] = here;
				return true;
			}
		}
		return false;
	}
}