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

문제

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

풀이

이분 매칭을 이용하여 해결할 수 있습니다.

초기값이 이렇게 되어있는 경우

• 1번 사람이 1번 노트북을 지목합니다.

• 2번 사람이 1번을 노트북을 지목합니다.
• 1번 사람은 1번 노트북 다음 3번 노트북을 지목합니다.

• 3번 사람이 1번 노트북을 지목합니다.
• 2번 사람은 1번 노트북 다음 2번 노트북을 지목합니다.

만약에 3번 사람이 1번 노트북을 지목했을 때 2번 사람이 다음 지목할 노트북이 없으면 3번이 다음 노트북을 지목합니다.(다음 노트북이 없으면 지목을 못합니다.)

코드

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

public class Main {

    public static int N, M;
    public static int[] occupy;
    public static boolean[] visited;
    public static ArrayList<Integer>[] myNotebook;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        visited = new boolean[N + 1];
        occupy = new int[N + 1];
        myNotebook = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            myNotebook[i] = new ArrayList<>();
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            myNotebook[Integer.parseInt(st.nextToken())].add(Integer.parseInt(st.nextToken()));
        }

        int ans = 0;
        for (int i = 1; i <= N; i++) {
            Arrays.fill(visited, false);
            if (dfs(i)) ans++;
        }

        System.out.println(ans);
        br.close();
    }

    public static boolean dfs(int num) {
        for (int i = 0; i < myNotebook[num].size(); i++) {
            int notebookNum = myNotebook[num].get(i);
            if (visited[notebookNum]) continue;
            visited[notebookNum] = true;

            if (occupy[notebookNum] == 0 || dfs(occupy[notebookNum])) {
                occupy[notebookNum] = num;
                return true;
            }
        }
        return false;
    }
}