[종만북] 졸업 학기

AC 코드입니다.

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
 
const int INF = 987654321;
int n, k, m, l;
//prerequisite[i] = i번째 과목의 선수과목 집합
int prerequisite[12];
//classes[i] = i번째 학기에 개설되는 과목의 집합
int classes[10];
int cache[10][1 << 12];
 
//n의 이진수 표현에서 켜진 비트의 수를 반환
int bitCount(int n) {
    if (n == 0) return 0;
    return n % 2 + bitCount(n / 2);
}
 
int graduate(int semester, int taken) {
    //기저 사례 : k개 이상의 과목을 이미 들은 경우
    if (bitCount(taken) >= k) return 0;
 
    //기저 사례 : m 학기가 전부 지난 경우 -> 못 듣는다
    if (semester == m) return INF;
    
    //메모이제이션
    int& ret = cache[semester][taken];
    if (ret != -1) return ret;
    ret = INF;
    
    //이번 학기에 들을 수 있는 과목 중 아직 듣지 않은 과목들을 찾기
    int canTake = (classes[semester] & ~taken);
 
    //선수 과목을 다 듣지 않은 과목들을 걸러낸다.
    for (int i = 0; i < n; i++) {
        if ((canTake & (1 << i)) &&
            (taken & prerequisite[i]) != prerequisite[i]) {
            canTake &= ~(1 << i);
        }
    }
    //이 집합의 모든 부분집합을 순회한다.
    for (int take = canTake; take > 0; take = ((take - 1) & canTake)) {
        if (bitCount(take) > l) continue;
        ret = min(ret, graduate(semester + 1, taken | take) + 1);
    }
    //이번 학기에 아무것도 듣지 않을 경우
    ret = min(ret, graduate(semester + 1, taken));
    return ret;
}
int main()
{
    int c; scanf("%d", &c);
    while (c--) {
 
        memset(cache, -1, sizeof(cache));
        memset(prerequisite, 0, sizeof(prerequisite));
        memset(classes, 0, sizeof(classes));
 
        scanf("%d %d %d %d", &n, &k, &m, &l);
 
        //각 과목의 정보
        for (int i = 0; i < n; i++) {
            int r; scanf("%d", &r); //선수 과목의 수
            for (int j = 0; j < r; j++) {
                int temp; scanf("%d", &temp);
                prerequisite[i] |= (1 << temp);
            }
        }
 
        //각 학기의 정보
        for (int i = 0; i < m; i++) {
            int t; scanf("%d", &t); //개설되는 과목의 수
            for (int j = 0; j < t; j++) {
                int temp; scanf("%d", &temp);
                classes[i] |= (1 << temp);
            }
        }
        int ans = 0;
        ans = graduate(0, 0);
        if (ans == INF) printf("IMPOSSIBLE\n");
        else printf("%d\n", ans);
    }
    return 0;
}

 

 

풀이

 

책에서 이 문제를 비트 마스크 파트에 넣은 이유는

비트 마스크를 이용해서 주어진 집합의 부분 집합을 순회하는 코드를 쉽게 작성할 수 있기 때문이다.

 

하지만 나는 브루트 포스와 dp의 굴레에서 헤어 나오지 못해 결국 책에 나온 코드를 보고 작성하였다.

 

문제에서 이용하는 비트 마스크 부분은 크게 네 가지이다.

 

1. 과목의 선수과목 저장 배열 (prerequisite)

2. 학기 별 들을 수 있는 과목 저장 배열(classes)

3. 들은 과목들을 저장할 int 형 변수(taken)

4. 비트를 세어주는 함수 (bitCount(int n))

 

우린 이들을 브루트 포스 과정에 이용해야 한다.

 

브루트 포스 부분만 간단히 요약하자면

 

1. 현재 학기에 들을 수 있는 과목 중 아직 듣지 않은 과목을 찾는다.

2. 듣지 않은 과목 중 선수 과목을 다 듣지 않은 과목들을 제외한다.

3. 1,2번 과정을 거쳐 정제된 과목들을 부분집합 순회를 이용하여 재귀 호출을 한다.

 

 예외 처리

1. 하나도 안 듣는 학기가 있을 수 있으므로, 그 부분은 바로 재귀 호출로 넘겨버린다.

2. 한 학기에 L개의 과목만 들을 수 있기 때문에 부분집합 순회를 할 때 그 부분집합 원소의 개수가 L을 초과하는 경우 continue 시킨다.

3. 재귀호출 중 M 학기가 지난 경우 버린다.

4. 문제에서 요구하는 k개 이상의 과목을 이미 들은 경우 0을 리턴하게 된다. (코드에서 재귀 호출 중 계속 +1을 해주고 있기 때문에 0을 리턴하는 게 맞다)

 

초록색 글씨로 쓰인 부분을 은 모두 비트 마스크를 이용합니다!

 

그다음 dp 부분이다.

 

dp를 쓰는 이유는 메모 이제이 션으로 최적화하기 위해 쓰는 것이기 때문에

2차원 dp (각 학기, 들은 과목들(taken)) 를 재귀 호출 과정에서 꾸준히 저장해줘야 합니다.

 

메모이제이션 처리

 

일반적인 메모이제이션 처리와 동일합니다!

 

정답으로 리턴할 변수 ret를 만들어 두고, 함수가 호출될 때마다 해당 학기와 들은 과목들을 저장해둡니다.

만약 이 값이 미리 캐시 배열 초기화할 때 만들어둔 -1 이 아니라면 (한 번 저장된 적이 있다면) 바로 ret를 리턴해 줍니다.

 

이제 간단히 요약을 했으니 좀 더 구체적으로 들어가 보자!

 

1. 이번 학기에 들을 수 있는 과목 중 아직 듣지 않은 과목들을 찾기

 

우린 앞서 i번째 학기에 들을 수 있는 과목을 classes 배열에 미리 초기화해두었고,

지금까지 들은 과목들을 taken 변수에 계속 넣어주었다.(비트 마스크 연산을 통해)

 

그렇다면, i번째 학기 때 아직 듣지 않은 과목들은 classes [i] & ~taken 연산을 통해

정확히 듣지 않은 과목만 뽑힌다.

 

2. 선수 과목을 다 듣지 않은 과목들을 찾기

 

위 1번 과정을 통해 우린 canTake 변수에 i번째 학기에 아직 듣지 않은 과목들을 정제해냈다!

 

따라서 이제 그 과목들 중 선수 과목들을 듣지 않은 과목들을 추출해내야 하는데

 

우린 앞서 과목 별 선수과목 배열을 만들어두었다(prerequisite)

 

모든 과목들을 순회하며 canTake와 일치하는지

&&

prerequisite와 taken 이 일치하는지

 

를 돌리면서 불일치 과목들을 canTake 변수에 빼주면 비로소 완벽한 i번째 학기 때 들을 수 있는 과목이 나오게 된다.

 

 

3. 부분 집합 순회

 

이제 canTake 변수(과목을 저장한 비트)를 완성했으므로,

이 변수를 이용해 모든 부분 집합을 순회하면서 재귀 호출만 시키면 된다.

 

우선 해당 코드를 보자.

//이 집합의 모든 부분집합을 순회한다.
    for (int take = canTake; take > 0; take = ((take - 1) & canTake)) {
        if (bitCount(take) > l) continue;
        ret = min(ret, graduate(semester + 1, taken | take) + 1);
    }
    //이번 학기에 아무것도 듣지 않을 경우
    ret = min(ret, graduate(semester + 1, taken));
    return ret;

비트에 대해 모든 부분 집합을 순회하는 방법은

 

완성된 비트에 대해서 -1씩 빼주면서 0이 되기 전까지 돌리는 것이다.

 

for 문의 변수 take가 변화하는 과정을 잘 보면,

take는 canTake(완성된 비트)에서 시작해 0보다 클 때까지 돌리며

그 과정에서 take - 1 & canTake 연산을 진행한다.

 

take - 1은 상당히 유용한 부분집합 순회 방식인데,

take 비트의 맨 오른쪽 비트를 0으로 바꾸는 대신, 그 보다 오른쪽 비트들을 모두 1로 바꿔준다.(없으면 그대로)

이 연산은 직접 해보면 이해가 빠를 것이다.

 

추가적으로 canTake와 & 연산을 진행하여 곧이곧대로 -1씩 옮겨지는 게 아닌, canTake와 맞는 비트 중 그다음 비트를 간추려내게 해 준다.

 

 

 

쉽게 쉽게 쓰는 척했지만 쓰면서 너무 어려웠다 ㅠㅠ

하지만 비트 마스크를 쓰는 부분을 그냥 일반적인 반복으로 돌렸다면 

코드도 훨씬 복잡하고 이해도 안 되었을 것 같다..

이 문제를 통해 비트 마스크를 왜 쓰는지 이제야 좀 알 것 같다.