[백준] 20119번: 클레어와 물약

경북대학교 고리콘 대회 문제 : www.acmicpc.net/contest/view/545

2020 경북대학교 Goricon

문제 주소 : www.acmicpc.net/problem/20119

20119번: 클레어와 물약

문제 확인

 

그래프 문제

시뮬레이션 문제처럼 주어진 대로 풀면 쉽게 풀리는 문제입니다.

레시피에서 필요한 물약들을 간선으로 만들고 가지고 있는 물약마다 간선을 제거하여 간선 수가 0이 될 시 가지고 있는 물약에 추가합니다.

문제 예시 중 이미 가지고 있는 물약을 레시피로 들고 있는 경우도 있는데 이를 위하여 중복체크를 해 주어야 합니다.

 

풀이

 

문제를 2개의 스텝으로 분리합니다.

1. 필요한 물약을 간선으로 두는 그래프 만들기
2. 가지고 있는 물약으로 간선을 제거하며 새로운 물약이 만들어지면 다음 루프로 진입, 만들어진 물약이 없다면 루프 종료

2번 스텝에서 간선을 제거하기 때문에 각 루프마다 가지고 있는 모든 물약을 탐색할 필요가 없습니다. 새로 생성된 물약만 체크하고 생성된 물약이 없다면 종료합니다. 모든 물약을 검사하게 되면 시간 초과가 발생합니다.

 

문제에서 오름차순으로 출력하라고 하여 set 혹은 map을 사용하게 되면 물약을 추가할 때마다 탐색을 하기 때문에 시간, 메모리 모두 비효율적입니다. 따라서 vector을 사용 후 마지막에 정렬합니다.

 

코드

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
#include <unistd.h>
namespace io {
    const signed IS = 1 << 22, OS = 1 << 20;
    char I[IS + 1], *J = I, O[OS], *K = O;
 
    inline void daer() { if (J >= I + IS - 64) { char*p = I; do*p++ = *J++; while (J != I + IS); p[read(0, p, I + IS - p)] = 0; J = I; } }
    template<int N = 10, typename T = int> inline T getu() { daer(); T x = 0; int k = 0; do x = x * 10 + *J - '0'; while (*++J >= '0'&&++k < N); ++J; return x; }
    template<int N = 10, typename T = int>inline  T geti() { daer(); bool e = *J == '-'; J += e; return(e ? -1 : 1)*getu<N, T>(); }
    inline void flush() { write(1, O, K - O); K = O; }
 
    template<int N = 10, typename T = int> inline void putu(T n) { char s[(N + 7) / 8 * 8], *p = s; int k = 0; do*p++ = n % 10 + 48; while ((n /= 10) && ++k < N); do*K++ = *--p; while (p != s); *K++ = 10; if (K >= O + OS - 64)flush(); }
    template<int N = 10, typename T = int> inline void puti(T n) { if (n < 0)*K++ = '-', n = -n; putu<N, T>(n); }
    struct f { f() { I[read(0, I, IS)] = 0; }~f() { flush(); } }flu;
};//출처 : https://cgiosy.github.io/posts/fast-io
using namespace io;
typedef struct recp {
    int size, id;
}recp;
int main() {
    int n = getu(), m = getu(), t;
    bool dup_check[200001] = { 0 }; //물약 중복 체크
    vector<int> res;
    vector<vector<int>>graph(n + 1);
    vector<recp> recp_list(m);
    for (int i = 0; i < m; i++) {
        recp_list[i].size = getu();//0이 될 시 완성
        for (int j = 0; j < recp_list[i].size; j++) {
            graph[getu()].push_back(i);//간선 생성
        }
        recp_list[i].id = getu();//물약 종류
    }
    t = getu();
    for (int i = 0; i < t; i++) {
        int tmp = getu();
        res.push_back(tmp);
        dup_check[tmp] = true;
    }
    int start = 0, end = res.size();
    do {
        for (int i = start; i < end; i++) {
            for (auto target : graph[res[i]]) {
                recp_list[target].size--; //중복체크를 하기 때문에 간선 개수로만 검사할 수 있음
                if (recp_list[target].size == 0 && !dup_check[recp_list[target].id]) {//물약 생성, 중복체크
                    res.push_back(recp_list[target].id);
                    dup_check[recp_list[target].id] = true;
                }
            }
        }
        start = end; //전에 검사한 물약은 다시 검사하지 않음
        end = res.size();
    } while (start != end);//생성된 물약이 없다면 종료
    sort(res.begin(), res.end());
 
    printf("%d\n", res.size());
    for (auto t : res)
        printf("%d ", t);
}