백준 1298 자바 - 노트북의 주인을 찾아서 (BOJ 1298 JAVA)

문제 : boj1298

 

 

  기본 형태의 이분매칭 문제이다. 그러니 푸는법을 모르겠다면 이분매칭에 대해 구글링해보면 풀 수 있다. 얼핏 이분 그래프가 아닌 것 같아 이분매칭을 적용하지 못한다고 생각할 수 있으나, 제시된 N이 결국 N명의 사람과 N개의 노트북 두개 모두를 뜻하므로 N개의 사람 정점과 N개의 노트북 정점이 이분 그래프를 이루게 된다.

 

 

코드 : github

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

public class Main {
    StringTokenizer st;
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private void tokenizing() throws Exception { st = new StringTokenizer(br.readLine()); }
    private int nextInt() { return Integer.parseInt(st.nextToken()); }

    ArrayList<Integer>[] edges;
    int[] matched, v;

    private boolean matching(int from) {
        for (int to : edges[from]) {
            if (v[to] != 0) continue;
            v[to] = 1;
            if (matched[to] == 0 || matching(matched[to])) {
                matched[to] = from;
                return true;
            }
        }
        return false;
    }

    private void solution() throws Exception {
        tokenizing();
        int n = nextInt();
        int m = nextInt();

        edges = new ArrayList[n+1];
        for (int i = 1; i <= n; i++) edges[i] = new ArrayList<>();
        while (m-->0) {
            tokenizing();
            edges[nextInt()].add(nextInt());
        }

        matched = new int[n+1];
        v = new int[n+1];

        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            if (matching(i)) {
                cnt++;
            }
            Arrays.fill(v, 0);
        }

        System.out.println(cnt);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}