백준 1575 자바 - 졸업 (BOJ 1575 JAVA)

문제 : https://www.acmicpc.net/problem/1575

코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/01500/BOJ_1575.java

 

  생각해야 할 부분이 많은 까다로운 문제였다. 그래도 1시간정도 걸렸으니 그저께 8시간 걸려 풀었던 문제 보다는 훨씬 나았다. 플래도 가끔씩 풀어지긴 하는데, 아직 내 실력으론 풀어도 보통 1시간 이상은 기본으로 걸리는 것 같다.

 

  나중에 한 번 틀리고 나서 본건데, 6개월 전부터 '맞았습니다'가 하나도 없는 문제였다. 미리 채점 현황을 봤다면 아예 시도를 안해봤을수도 있을듯 ㄷㄷ 처음에 틀리고 나서는 나도 저 중에 하나가 되겠거니 했는데, 자기 전에 맞아서 꿀잠 잘 것 같다.

 

0. 일단 이 문제에서 사용한 구현 방식은 네트워크 플로우인데, 이분 매칭으로 가능하다. 우선 해설을 설명하기 전에 이분 매칭의 아이디어는 다음과 같다. 이분 매칭을 이미 알고 있다면 '1.'로 넘어가면 된다. 우선 시작은 아래와 같은 그래프이다. N을 M에 매칭 시킬 때, 어떻게 매칭 시켜야 더 많은 N을 매칭 시킬 수 있는지에 대한 아이디어가 이분 매칭 이다.

 

 우선 0의 간선들에 대해 dfs를 진행한다. a를 보게되고, 아무도 차지하지 않고 있으므로 매칭시킨다.

 

다음으로 1을 매칭시키기 위해 다시 탐색을 진행한다. 우선 a를 보니 이미 0이 차지하고 있다. 이 때 이미 차지하고 있던 0에서 다시 bfs를 진행해서 다른 자리로 비킬 수 있는지 확인한다. b로 갈 수 있으므로, 0을 b로 매칭시키고 1을 자리가 비게 된 a와 매칭시킨다. (파란선은 현재 없어진 매칭을 나타낸다.)

 

이번엔 2에 대해 dfs를 진행한다. 이 때 a는 현재 '1'이 차지하고 있으므로 다른 자리로 갈 수 있는지 확인한다. 이제 1에 대해 다시 dfs를 진행하고(재귀적으로), b를 보니 0이 차지하고 있다. 0에게 다시 다른 자리로 갈 수 있는지 확인해달라고 하고, 0에서 다시 dfs를 진행하여 0은 c와 매칭된다. 그리고 빈 b를 1이 차지하고, 2도 빈 a를 차지할 수 있게 된다. 위의 과정을 코드로 구현하면 N을 최대한 많은 M에 매칭 시킬 수 있게 된다.

 

 

 

 

1. 그럼 이제 다시 요 문제의 해설로 돌아오겠다. 이 문제를 어렵게 만든 조건들은 다음과 같다.

1.A 이미 들었던 수업이 있다. (영향도 : 중)

1.B 졸업 가능한 수업을 들었더라도, 수업의 개수를 최소로 출력해야 한다. (영향도 : 하)

1.C 사전 순으로 앞서는 순서로 출력해야 한다. (영향도 : 상)

 

 

 

2. 일단 위의 내용을 모두 무시하고 단순히 졸업 가능한 수업 수만 채우려면 어떻게 해야할지부터 생각해보자. 졸업 조건을 An이라고 할 때, 문제의 '예제 입력 1'은 다음과 같이 그릴 수 있다.

A1은 '2 3 1 2 3'에 해당하고, A2는 '2 3 3 4 5'에 해당한다. 그래프에 A1과 A2가 두 개씩 있는 것은, 둘 다 2개의 수업을 들어야 하기 때문이다. 이제 위에서 말한 '이분 매칭' 방식을 진행하면서 만약 좌측의 A1, A1, A2, A2 중 하나라도 매칭에 실패한다면 졸업이 불가하므로 '-1'을 출력하고 끝내면 된다.

 

 

그럼 여기에 '1.A 이미 들었던 수업이 있다.' 를 생각해보자. 이 경우, dfs를 위에서 아래로 진행할 것이므로 입력받은 이미 들었던 수업을 아래 그림과 같이 그래프에서 위로 올려버리면 된다. 이미 들었던 수업부터 매칭을 할 것이고, 출력에서 이미 들었던 수업은 제외하고 출력하면 될 것이다.

 

다음으로 '1.B 졸업 가능한 수업을 들었더라도, 수업의 개수를 최소로 출력해야 한다.' 를 생각해보자. 사실 좌측에서 우측으로의 매칭에서 좌측에 무조건 만족시켜야 하는 졸업 조건만을 적어 뒀고, 졸업 조건 중 하나라도 매칭이 안된다면 졸업이 불가능하므로 졸업 조건이 모두 매칭만 된다면 1.B는 자동적으로 만족할 수 있다.

 

 

그럼 '1.C 사전 순으로 앞서는 순서로 출력해야 한다.'를 생각해보자. 이 부분에서 상당히 막혔었다. 단순히 우측을 이미 들었던 수업도 정렬해서 넣고, 들어야 하는 수업들도 정렬해서 놓고 돌리면 될꺼라 생각했는데, 틀렸다 ㅠ.

위의 내용까지의 코드는 아래와 같다. 요기 위까지 나왔던 내용은 모두 담고 있다.

 

(아래는 틀린(WA) 코드임)

import java.io.DataInputStream;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;

public class Main {
    private static boolean[] v;
    private static int[] matched;
    private static ArrayList<Integer>[] edge;

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

    private static void solution() throws Exception {
        int tmp = nextInt();
        HashSet<Integer> hs = new HashSet<>();
        while (tmp-->0) hs.add(nextInt());
        matched = new int[101];
        Arrays.fill(matched, -1);

        int n = nextInt();
        int[] remain = new int[n];
        edge = new ArrayList[n];
        ArrayList<Integer>[] edgeTmp = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            edge[i] = new ArrayList<>();
            edgeTmp[i] = new ArrayList<>();
        }

        for (int i = 0; i < n; i++) {
            remain[i] = nextInt();
            tmp = nextInt();
            int[] cNum = new int[tmp];
            for (int j = 0; j < tmp; j++) cNum[j] = nextInt();
            Arrays.sort(cNum);
            for (int j = 0; j < tmp; j++) {
                int cur = cNum[j];
                if (hs.contains(cur))
                    edge[i].add(cur);
                else
                    edgeTmp[i].add(cur);
            }
            edge[i].addAll(edgeTmp[i]);
        }

        for (int i = 0; i < n; i++) {
            while (remain[i]-->0) {
                v = new boolean[101];
                if (!matching(i)) {
                    System.out.println("-1");
                    return;
                }
            }
        }

        int cnt = 0;
        StringBuilder answer = new StringBuilder();
        for (int i = 1; i <= 100; i++) {
            if (hs.contains(i) || matched[i] == -1) continue;
            cnt++;
            answer.append(i).append(' ');
        }
        System.out.println(cnt);
        System.out.println(answer);
    }

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

    private static final int DEFAULT_BUFFER_SIZE = 1 << 16;
    private static DataInputStream inputStream;
    private static byte[] buffer;
    private static int curIdx, maxIdx;

    private static void initFI() {
        inputStream = new DataInputStream(System.in);
        buffer = new byte[DEFAULT_BUFFER_SIZE];
        curIdx = maxIdx = 0;
    }

    private static int nextInt() throws IOException {
        int ret = 0;
        byte c = read();
        while (c <= ' ') c = read();
        do {
            ret = ret * 10 + c - '0';
        } while ((c = read()) >= '0' && c <= '9');
        return ret;
    }

    private static byte read() throws IOException {
        if (curIdx == maxIdx) {
            maxIdx = inputStream.read(buffer, curIdx = 0, DEFAULT_BUFFER_SIZE);
            if (maxIdx == -1) buffer[0] = -1;
        }
        return buffer[curIdx++];
    }
}

 

 

3. 그럼 위의 과정으로 '1.C 사전 순으로 앞서는 순서로 출력해야 한다.'가 처리 안된다면 어떻게 해야 할까? 졸업 조건에서 수업으로 매칭은 정렬을 해도 사전순이 아닐 수 있다. 그러므로, 수업에서 졸업 조건으로 매칭시켜야 한다. 이렇게 하면 수업을 정렬시켜둔 상태로 순서대로 dfs를 돌리며 이분 매칭을 시켜 사전순을 만들 수 있다. 전체에 대한 네트워크 플로우 그래프를 그려보면 다음과 같다. 다만 유량과 용량이 고정이고 (A1,A2를 졸업 조건의 수대로 쪼갰으므로), 수업 부분에 들어오는 또 다른 플로우가 없으므로 여전히 이분 매칭으로 풀 수 있다.

코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/01500/BOJ_1575.java

 

이 때 already는 이미 들었던 수업이다(코드의 already). lecture는 그 이외의 수업들이다(코드의 lecture). 일단 already쪽으로 진행해 이미 들었던 수업부터 매칭시킨다(코드의 53~58 line). 다음으로 lecture쪽으로 진행해 다른 수업들을 '수업 번호가 낮은 번호부터 높은 번호 순으로 매칭시킨다(코드의 60~66 line). 이 때, 매칭된 갯수(코드의 cnt)가 졸업 조건에서 들어야 하는 수업의 총 수(코드의 idx)보다 낮다면 졸업이 불가하다. (-1 출력, 69~72 line)

 

  매칭된 번호의 출력 역시 순서대로 해야 한다. 이 코드에서 sort 함수를 볼 수 없는데, 그건 어차피 총 수업의 수가 1~100까지의 100개가 전부라, 그냥 배열을 순서대로 순회를 하는 방식으로 짰기 때문이다(어차피 최대 100번만 보면 되므로 시간 차이도 거의 없음).