ALLERGY (상, p. 428)

문제#

image.png

어떻게 풀었나?#

이 문제는 NP-complete인 set cover문제이다. 그럼에도 불구하고 PS문제로 나왔다는 것은 적당한 가지치기로 Time을 많이 줄일 수 있음을 의미할 것이다. 모든 경우의 수를 계산해보면, 음식마다 요리할지 말지를 결정하면 되므로 $O(2^{50})$인데, 일단 가지치기는 나중에 생각해보고 모든 경우의 수를 다 하도록 구현먼저 했다.

가지치기 1#

모든 경우의 수를 다 탐색하는 방식으로 코드를 구현하고 나서, dfs 탐색 중 지금까지 구한 정답보다 더 많은 음식을 요리해야 하는 상황이면 탐색을 중단하고, 음식을 선택하지 않는 탐색보다 음식을 선택하는 탐색을 먼저 진행하도록 하면 AC를 받을 수 있다. (결과: 2440ms)

가지치기 2#

다음 음식을 요리할지 말지 결정할 때 그냥 다음 번호의 요리를 선택하는 것이 아니라, 아직까지 아무것도 먹지 않은 사람들을 반복문 돌면서 그 사람이 먹지 않은 음식들 중 하나를 고르는데, 그 음식을 먹을 수 있는 사람들이 가장 많은 음식을 고른다. (결과 1600ms)

가지치기 3#

어떤 음식을 먹을 수 있는 사람들이 다른 음식을 먹을 수 있는 사람들을 완전히 포함한다면, 후자의 음식은 탐색 대상에서 제외한다. (결과: 668ms)

가지치기 4#

첫번째 음식 선택할 때에도 가치지기2와 같은 기준으로 음식을 선택한다. (결과: 520ms)

가지치기 5#

dfs 탐색중 다음 음식 고르는 방법을 바꿔본다. 음식을 아직 못 먹은 사람들 중에서 먹을 수 있는 음식 수가 가장 적은 사람들을 택하고, 그 사람들이 먹을 수 있는 음식 중 가장 많은 사람들이 먹을 수 있는 음식을 택하도록 했다. (결과: 8ms)

DP를 이용한 가지치기 방법#

핵심 아이디어#

음식을 기준으로 탐색을 하게 되면, 위와 같이 여러가지 복잡한 가지치기 방법으로 탐색 공간을 줄여야 한다. 하지만 사람 기준으로 탐색하게 되면 탐색 공간이 확 줄어들게 된다. 왜냐하면, 한 사람이 먹는 음식들을 고를 때 다른 사람들도 같이 cover되기 때문에, 이렇게 같이 cover되는 다른 사람들은 탐색할 필요가 없게 되기 때문이다.

상태 공간#

dp[pno] = 0부터 pno까지 탐색하면서 찾은 최소 음식 수 상한

Set Cover 여부 → bit mask로 표현#

n이 50밖에 되지 않기 때문에 어떤 음식을 먹는 사람들의 집합을 unsigned long long 비트로 표현할 수 있다.

정답 코드#

1) 2440ms AC 코드#

//2440ms
#include <bits/stdc++.h>
using namespace std;
const int NA = -1;
const int INF = 0x3f3f3f3f;
int n, m;
string p[51];
unordered_map<string, int> pno_by_p;
vector<vector<int>> pno_set_by_fno;
int pno_chk[51];
int ans;
inline void Init(int n, int m) {
    pno_by_p.clear();
    pno_set_by_fno.clear();
    pno_set_by_fno.resize(m);
    memset(pno_chk, 0, sizeof(pno_chk));
    ans = INF;
}
void Dfs(int fno, int food_cnt, int person_cnt) {
    if(food_cnt >= ans) return;
    if(person_cnt == n) {
        ans = min(ans, food_cnt);
        return;
    }
    if(fno==m) return;

    int pcnt=0;
    for(int i=0; i<pno_set_by_fno[fno].size(); i++) {
        int pno = pno_set_by_fno[fno][i];
        if (!pno_chk[pno]) pcnt++;
        pno_chk[pno]++;
    }
    Dfs(fno+1, food_cnt+1, person_cnt+pcnt); //fno를 먹은 경우
    for(int i=0; i<pno_set_by_fno[fno].size(); i++) {
        int pno = pno_set_by_fno[fno][i];
        pno_chk[pno]--;
    }
    Dfs(fno+1, food_cnt, person_cnt); //fno를 안먹은 경우
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int tc; cin >> tc;
    while (tc--) {
        cin >> n >> m;
        Init(n, m);
        for(int pno=0; pno<n; pno++) {
            cin >> p[pno];
            pno_by_p[p[pno]] = pno;
        }
        string person;
        for(int fno=0; fno<m; fno++) {
            int cnt; cin >> cnt;
            for (int z = 0; z < cnt; z++) {
                cin >> person;
                pno_set_by_fno[fno].push_back(pno_by_p[person]);
            }
        }

        Dfs(0,0,0);
        printf("%d\n", ans);
    }
    return 0;
}

2) 1600ms AC 코드#

#include <bits/stdc++.h>
using namespace std;
const int NA = -1;
const int INF = 0x3f3f3f3f;
int n, m;
string p[51];
unordered_map<string, int> pno_by_p;
vector<vector<int>> pno_list_by_fno;
int pno_chk[51];
int ans;
vector<vector<int>> fno_list_by_pno;
bool fno_chk[51];

inline void Init(int n, int m) {
    pno_by_p.clear();

    pno_list_by_fno.clear(); pno_list_by_fno.resize(m);

    memset(pno_chk, 0, sizeof(pno_chk));
    ans = INF;

    fno_list_by_pno.clear(); fno_list_by_pno.resize(n);

    memset(fno_chk, false, sizeof(fno_chk));
}

void Dfs(int fno, int food_cnt, int person_cnt) {
    if(food_cnt >= ans) return;
    if(person_cnt == n) {
        ans = min(ans, food_cnt);
        return;
    }
    if(fno<0) return;
    //if(fno==m) return;

    fno_chk[fno] = true;

    //일단 fno를 요리한다.
    int pcnt=0;
    for (int s_pno : pno_list_by_fno[fno]) {
        if (!pno_chk[s_pno]) pcnt++;
        pno_chk[s_pno]++;
    }

    //음식을 아직 아무것도 먹지 않은 사람들 중 하나를 택해서,
    //그 사람이 먹지 않은 음식들 중 하나를 고르는데,
    //그 음식을 먹을 수 있는 사람들이 가장 많은 음식으로 고른다.
    int mx=-1, nfno=-1;
    for(int pno=0; pno<n; pno++) {
        if(pno_chk[pno]) continue;
        for(int nxt_fno : fno_list_by_pno[pno]) {
            if(fno_chk[nxt_fno]) continue;
            //이미 탐색한 음식인지만 체크하면 됨.
            if(mx < (int)pno_list_by_fno[nxt_fno].size()) {
                mx = (int)pno_list_by_fno[nxt_fno].size();
                nfno = nxt_fno;
            }
        }
    }
    Dfs(nfno, food_cnt + 1, person_cnt + pcnt);

    for (int s_pno : pno_list_by_fno[fno]) {
        pno_chk[s_pno]--;
    }
    Dfs(nfno, food_cnt, person_cnt);
    fno_chk[fno] = false;
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int tc; cin >> tc;
    while (tc--) {
        cin >> n >> m;
        Init(n, m);
        for(int pno=0; pno<n; pno++) {
            cin >> p[pno];
            pno_by_p[p[pno]] = pno;
        }
        string person;
        for(int fno=0; fno<m; fno++) {
            int cnt; cin >> cnt;
            for (int z = 0; z < cnt; z++) {
                cin >> person;
                pno_list_by_fno[fno].push_back(pno_by_p[person]);
                fno_list_by_pno[pno_by_p[person]].push_back(fno);
            }
        }

        Dfs(0,0,0);
        printf("%d\n", ans);
    }
    return 0;
}

3) 668ms AC 코드#

#include <bits/stdc++.h>
using namespace std;
const int NA = -1;
const int INF = 0x3f3f3f3f;
int n, m;
string p[51];
unordered_map<string, int> pno_by_p;
vector<vector<int>> pno_list_by_fno;
int pno_chk[51];
int ans;
vector<vector<int>> fno_list_by_pno;
bool fno_chk[51];

inline void Init(int n, int m) {
    pno_by_p.clear();

    pno_list_by_fno.clear(); pno_list_by_fno.resize(m);

    memset(pno_chk, 0, sizeof(pno_chk));
    ans = INF;

    fno_list_by_pno.clear(); fno_list_by_pno.resize(n);

    memset(fno_chk, false, sizeof(fno_chk));
}

void Dfs(int fno, int food_cnt, int person_cnt) {
    if(food_cnt >= ans) return;
    if(person_cnt == n) {
        ans = min(ans, food_cnt);
        return;
    }
    if(fno<0) return;
    //if(fno==m) return;

    fno_chk[fno] = true;

    //일단 fno를 요리한다.
    int pcnt=0;
    for (int s_pno : pno_list_by_fno[fno]) {
        if (!pno_chk[s_pno]) pcnt++;
        pno_chk[s_pno]++;
    }

    //음식을 아직 아무것도 먹지 않은 사람들 중 하나를 택해서,
    //그 사람이 먹지 않은 음식들 중 하나를 고르는데,
    //그 음식을 먹을 수 있는 사람들이 가장 많은 음식으로 고른다.
    int mx=-1, nfno=-1;
    for(int pno=0; pno<n; pno++) {
        if(pno_chk[pno]) continue;
        for(int nxt_fno : fno_list_by_pno[pno]) {
            if(fno_chk[nxt_fno]) continue;
            //이미 탐색한 음식인지만 체크하면 됨.
            if(mx < (int)pno_list_by_fno[nxt_fno].size()) {
                mx = (int)pno_list_by_fno[nxt_fno].size();
                nfno = nxt_fno;
            }
        }
    }
    Dfs(nfno, food_cnt + 1, person_cnt + pcnt);

    for (int s_pno : pno_list_by_fno[fno]) {
        pno_chk[s_pno]--;
    }
    Dfs(nfno, food_cnt, person_cnt);
    fno_chk[fno] = false;
}
int Include(int x, int y) {
    if(pno_list_by_fno[x].size()<pno_list_by_fno[y].size()) swap(x,y);

    int cnt=0;
    for(int i=0,j=0; i<pno_list_by_fno[y].size(); i++) {
        while(j<pno_list_by_fno[x].size() && pno_list_by_fno[x][j] != pno_list_by_fno[y][i]) j++;
        if(pno_list_by_fno[x][j] == pno_list_by_fno[y][i]) cnt++;
        j++;
    }

    if(cnt == pno_list_by_fno[y].size()) return y;
    return -1;
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int tc; cin >> tc;
    while (tc--) {
        cin >> n >> m;
        Init(n, m);
        for(int pno=0; pno<n; pno++) {
            cin >> p[pno];
            pno_by_p[p[pno]] = pno;
        }
        string person;
        for(int fno=0; fno<m; fno++) {
            int cnt; cin >> cnt;
            for (int z = 0; z < cnt; z++) {
                cin >> person;
                pno_list_by_fno[fno].push_back(pno_by_p[person]);
                fno_list_by_pno[pno_by_p[person]].push_back(fno);
            }
        }

        for(int fno=0; fno<m; fno++) {
            sort(pno_list_by_fno[fno].begin(), pno_list_by_fno[fno].end());
        }

        for(int i=0; i<m; i++) {
            if(fno_chk[i]) continue;
            for(int j=i+1; j<m; j++) {
                if(fno_chk[j]) continue;
                int tmp = Include(i,j);
                if(tmp == i) fno_chk[i]=true;
                else if(tmp == j) fno_chk[j]=true;
            }
        }
    
        Dfs(0,0,0);
        printf("%d\n", ans);
    }
    return 0;
}

4) 520ms AC 코드#

#include <bits/stdc++.h>
using namespace std;
const int NA = -1;
const int INF = 0x3f3f3f3f;
int n, m;
string p[51];
unordered_map<string, int> pno_by_p;
vector<vector<int>> pno_list_by_fno;
int pno_chk[51];
int ans;
vector<vector<int>> fno_list_by_pno;
bool fno_chk[51];

inline void Init(int n, int m) {
    pno_by_p.clear();

    pno_list_by_fno.clear(); pno_list_by_fno.resize(m);

    memset(pno_chk, 0, sizeof(pno_chk));
    ans = INF;

    fno_list_by_pno.clear(); fno_list_by_pno.resize(n);

    memset(fno_chk, false, sizeof(fno_chk));
}

int ChooseNextFno() {
    int mx=-1, nfno=-1;
    for(int pno=0; pno<n; pno++) {
        if(pno_chk[pno]) continue;
        //아직 아무것도 못먹은 친구들 중에서
        for(int nxt_fno : fno_list_by_pno[pno]) {
            if(fno_chk[nxt_fno]) continue;
            //가장 많은 사람이 먹을 수 있는 음식을 고른다.
            if(mx < (int)pno_list_by_fno[nxt_fno].size()) {
                mx = (int)pno_list_by_fno[nxt_fno].size();
                nfno = nxt_fno;
            }
        }
    }
    return nfno;
}

void Dfs(int fno, int food_cnt, int person_cnt) {
    if(food_cnt >= ans) return;
    if(person_cnt == n) {
        ans = min(ans, food_cnt);
        return;
    }
    if(fno<0) return;
    //if(fno==m) return;

    fno_chk[fno] = true;

    //일단 fno를 요리한다.
    int pcnt=0;
    for (int s_pno : pno_list_by_fno[fno]) {
        if (!pno_chk[s_pno]) pcnt++;
        pno_chk[s_pno]++;
    }

    //음식을 아직 아무것도 먹지 않은 사람들 중 하나를 택해서,
    //그 사람이 먹지 않은 음식들 중 하나를 고르는데,
    //그 음식을 먹을 수 있는 사람들이 가장 많은 음식으로 고른다.
    int nfno = ChooseNextFno();
    Dfs(nfno, food_cnt + 1, person_cnt + pcnt);

    for (int s_pno : pno_list_by_fno[fno]) {
        pno_chk[s_pno]--;
    }
    Dfs(nfno, food_cnt, person_cnt);
    fno_chk[fno] = false;
}
int Include(int x, int y) {
    if(pno_list_by_fno[x].size()<pno_list_by_fno[y].size()) swap(x,y);

    int cnt=0;
    for(int i=0,j=0; i<pno_list_by_fno[y].size(); i++) {
        while(j<pno_list_by_fno[x].size() && pno_list_by_fno[x][j] != pno_list_by_fno[y][i]) j++;
        if(pno_list_by_fno[x][j] == pno_list_by_fno[y][i]) cnt++;
        j++;
    }

    if(cnt == pno_list_by_fno[y].size()) return y;
    return -1;
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int tc; cin >> tc;
    while (tc--) {
        cin >> n >> m;
        Init(n, m);
        for(int pno=0; pno<n; pno++) {
            cin >> p[pno];
            pno_by_p[p[pno]] = pno;
        }
        string person;
        for(int fno=0; fno<m; fno++) {
            int cnt; cin >> cnt;
            for (int z = 0; z < cnt; z++) {
                cin >> person;
                pno_list_by_fno[fno].push_back(pno_by_p[person]);
                fno_list_by_pno[pno_by_p[person]].push_back(fno);
            }
        }

        for(int fno=0; fno<m; fno++) {
            sort(pno_list_by_fno[fno].begin(), pno_list_by_fno[fno].end());
        }

        for(int i=0; i<m; i++) {
            if(fno_chk[i]) continue;
            for(int j=i+1; j<m; j++) {
                if(fno_chk[j]) continue;
                int tmp = Include(i,j);
                if(tmp == i) fno_chk[i]=true;
                else if(tmp == j) fno_chk[j]=true;
            }
        }

        int nfno = ChooseNextFno();
        Dfs(nfno,0,0);
        printf("%d\n", ans);
    }
    return 0;
}

5) 8ms AC 코드#

#include <bits/stdc++.h>
using namespace std;
const int NA = -1;
const int INF = 0x3f3f3f3f;
int n, m;
string p[51];
unordered_map<string, int> pno_by_p;
vector<vector<int>> pno_list_by_fno;
int pno_chk[51];
int ans;
vector<vector<int>> fno_list_by_pno;
bool fno_chk[51];

inline void Init(int n, int m) {
    pno_by_p.clear();

    pno_list_by_fno.clear(); pno_list_by_fno.resize(m);

    memset(pno_chk, 0, sizeof(pno_chk));
    ans = INF;

    fno_list_by_pno.clear(); fno_list_by_pno.resize(n);

    memset(fno_chk, false, sizeof(fno_chk));
}

int ChooseNextFno() {
    int mn=INF, nfno=-1, mx=-1;
    for(int pno=0; pno<n; pno++) {
        if(pno_chk[pno]) continue;
        int fcnt=0;
        for(int nxt_fno : fno_list_by_pno[pno]) {
            if(fno_chk[nxt_fno]) continue;
            fcnt++;
        }
        if(mn > fcnt) {
            mn = fcnt;

            mx = -1;
            for(int nxt_fno : fno_list_by_pno[pno]) {
                if (fno_chk[nxt_fno]) continue;
                if(mx < (int)pno_list_by_fno[nxt_fno].size()) {
                    mx = (int)pno_list_by_fno[nxt_fno].size();
                    nfno = nxt_fno;
                }
            }
        }
        else if(mn == fcnt) {
            for(int nxt_fno : fno_list_by_pno[pno]) {
                if (fno_chk[nxt_fno]) continue;
                if(mx < (int)pno_list_by_fno[nxt_fno].size()) {
                    mx = (int)pno_list_by_fno[nxt_fno].size();
                    nfno = nxt_fno;
                }
            }
        }
    }
    return nfno;
}

void Dfs(int fno, int food_cnt, int person_cnt) {
    if(food_cnt >= ans) return;
    if(person_cnt == n) {
        ans = min(ans, food_cnt);
        return;
    }
    if(fno<0) return;
    //if(fno==m) return;

    fno_chk[fno] = true;

    //일단 fno를 요리한다.
    int pcnt=0;
    for (int s_pno : pno_list_by_fno[fno]) {
        if (!pno_chk[s_pno]) pcnt++;
        pno_chk[s_pno]++;
    }

    //음식을 아직 아무것도 먹지 않은 사람들 중
    //먹을 수 있는 음식이 가장 적은 사람을 택한다.
    //그 사람이 먹지 않은 음식들 중 하나를 고르는데,
    //그 음식을 먹을 수 있는 사람들이 가장 많은 음식으로 고른다.
    int nfno = ChooseNextFno();
    Dfs(nfno, food_cnt + 1, person_cnt + pcnt);

    for (int s_pno : pno_list_by_fno[fno]) {
        pno_chk[s_pno]--;
    }
    Dfs(nfno, food_cnt, person_cnt);
    fno_chk[fno] = false;
}
int Include(int x, int y) {
    if(pno_list_by_fno[x].size()<pno_list_by_fno[y].size()) swap(x,y);

    int cnt=0;
    for(int i=0,j=0; i<pno_list_by_fno[y].size(); i++) {
        while(j<pno_list_by_fno[x].size() && pno_list_by_fno[x][j] != pno_list_by_fno[y][i]) j++;
        if(pno_list_by_fno[x][j] == pno_list_by_fno[y][i]) cnt++;
        j++;
    }

    if(cnt == pno_list_by_fno[y].size()) return y;
    return -1;
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int tc; cin >> tc;
    while (tc--) {
        cin >> n >> m;
        Init(n, m);
        for(int pno=0; pno<n; pno++) {
            cin >> p[pno];
            pno_by_p[p[pno]] = pno;
        }
        string person;
        for(int fno=0; fno<m; fno++) {
            int cnt; cin >> cnt;
            for (int z = 0; z < cnt; z++) {
                cin >> person;
                pno_list_by_fno[fno].push_back(pno_by_p[person]);
                fno_list_by_pno[pno_by_p[person]].push_back(fno);
            }
        }

        for(int fno=0; fno<m; fno++) {
            sort(pno_list_by_fno[fno].begin(), pno_list_by_fno[fno].end());
        }

        for(int i=0; i<m; i++) {
            if(fno_chk[i]) continue;
            for(int j=i+1; j<m; j++) {
                if(fno_chk[j]) continue;
                int tmp = Include(i,j);
                if(tmp == i) fno_chk[i]=true;
                else if(tmp == j) fno_chk[j]=true;
            }
        }

        int nfno = ChooseNextFno();
        Dfs(nfno,0,0);
        printf("%d\n", ans);
    }
    return 0;
}

6) 12ms DP AC 코드#

  • pset_by_fno[fno]: 음식 fno를 선택하면 먹을 수 있게 되는 사람들의 비트마스크
  • fno_list_by_pno[pno]: 사람 pno가 먹을 수 있는 음식 목록
  • visit: 지금까지 선택한 음식들로 “먹을 수 있게 된 사람들” 비트마스크
#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
unordered_map<string, int> pno_by_pname;

const int INF = 0x3f3f3f3f;

int n,m;
int fno_list_by_pno[51][51];
int fnoN_by_pno[51];
ull pset_by_fno[51];
int dp[51];

void Init() {
    pno_by_pname.clear();
    memset(pset_by_fno, 0, sizeof(pset_by_fno));
    memset(dp, 0x3f, sizeof(dp));
    memset(fnoN_by_pno, 0, sizeof(fnoN_by_pno));
}

int Dfs(int pno, int fcnt, ull visit) {
    if(visit == (1ULL<<n)-1) {
        return fcnt;
    }
    if(pno == n) return INF;
    if(fcnt >= dp[pno]) return INF;

    int & ret = dp[pno];
    if(visit & (1ULL<<pno)) return ret = min(ret, Dfs(pno+1, fcnt, visit));
    //이미 다른 사람 탐색할 때, 이 사람(pno)이 먹을 수 있는 음식을 먹어버렸다.
    //따라서 이 사람은 음식을 고를 필요가 없다.

    for(int i=0; i<fnoN_by_pno[pno]; i++) {
        int fno = fno_list_by_pno[pno][i]; //pno사람이 먹는 음식(fno)
        ret = min(ret, Dfs(pno+1, fcnt+1, visit|pset_by_fno[fno]));
    }
    return ret;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int tc; cin >> tc;
    while(tc--) {
        Init();
        cin >> n >> m;

        string in;
        for(int pno=0; pno<n; pno++) {
            cin >> in;
            pno_by_pname[in] = pno;
        }

        for(int fno=0; fno<m; fno++) {
            int cnt; cin >> cnt;
            for(int i=0; i<cnt; i++) {
                cin >> in;
                int pno = pno_by_pname[in];
                fno_list_by_pno[pno][fnoN_by_pno[pno]++] = fno;
                pset_by_fno[fno] |= (1ULL << pno);
            }
        }

        printf("%d\n", Dfs(0,0,0));
    }
    return 0;
}

Comment#

회사 써티 Expert 문제를 푸는 느낌이었고, 많은 가지치기 기법을 배울 수 있었다.

Backward BOARDCOVER2 (상, p. 422) KMP Forward