[자바] 백준 11377 - 열혈강호 3 (java)

 문제 : boj11377

---

 

필요 알고리즘 개념

• 이분매칭
  
  • 네트워크 플로우에서 이분 그래프일 시 사용 가능한 이분매칭 알고리즘을 통해 풀 수 있다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  우선 N명의 직원이 M개의 일을 선택하는 것만 생각하자. 그럼 기본적인 형태의 이분매칭 알고리즘을 적용해서 풀 수 있다. 여기서 문제가 되는건 N명 중 K명은 일을 최대 2개할 수 있다는 점인데, 사실 약간의 아이디어만 추가하면 똑같다. 최대 K번에 걸쳐 이분매칭 알고리즘을 한번 더 적용하면 된다.

 

// 우선 이분매칭을 통해 하나의 일을 수행하자.
v = new boolean[m+1];
matched = new int[m+1];
Arrays.fill(matched, -1);
int cnt = 0;
for (int i = 1; i <= n; i++) {
    if (matching(i)) {
        cnt++;
        v = new boolean[m+1];
    }
}


// 그리고 최대 k번에 걸쳐 다시한번 이분매칭을 진행하면 된다.
v = new boolean[m+1];
for (int i = 1; i <= n && k > 0; i++) {
    if (matching(i)) {
        cnt++;
        k--;
        v = new boolean[m+1];
    }
}

 

 

---

 

코드 : github

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

public class Main {
    int n, m;
    int[] matched;
    ArrayList<Integer>[] edges;
    boolean[] v;

    private boolean matching(int cur) {
        for (int next : edges[cur]) {
            if (v[next]) continue;
            v[next] = true;
            if (matched[next] == -1 || matching(matched[next])) {
                matched[next] = cur;
                return true;
            }
        }
        return false;
    }

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        edges = new ArrayList[n+1];
        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            edges[i] = new ArrayList<>(a);
            while (a-->0) {
                edges[i].add(Integer.parseInt(st.nextToken()));
            }
        }

        v = new boolean[m+1];
        matched = new int[m+1];
        Arrays.fill(matched, -1);
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            if (matching(i)) {
                cnt++;
                v = new boolean[m+1];
            }
        }

        v = new boolean[m+1];
        for (int i = 1; i <= n && k > 0; i++) {
            if (matching(i)) {
                cnt++;
                k--;
                v = new boolean[m+1];
            }
        }

        System.out.println(cnt);
    }

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