본문 바로가기

전체 글

BOJ)4196 도미노 문제:icpc.me/4196 X번 블록이 넘어지면 Y번 블록이 넘어지는 정보가 여러개 주어질 때 도미노를 직접 넘어뜨려야하는 최소 블록 개수를 출력하는 문제이다. 도미노를 직접 넘어뜨려야 한다는 건 결국 다른 도미노에 의해서 넘어지지 않는다는걸 의미하는데 이는 곧 indegree가 0인 정점의 개수다. 또 하나 고려해줘야 하는 경우가 있는데 cycle을 이룰 경우 indegree가 0이지 않지만 누가 먼저 넘어지지 않는 이상 영원히 넘어지지 않는다. 따라서 우리는 방향 그래프에서 SCC를 구해준 후 SCC로 이루어진 그래프에서 indegree가 0인 SCC의 개수를 세어주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839.. 더보기
BOJ)3665 최종 순위 문제:icpc.me/3665 작년의 등수가 주어지고 올해 등수가 역전 된 두 팀의 목록이 주어질 때 올해 순위를 발표하는 문제이다. 우선 작년의 등수를 기반으로 n^2의 방법으로 간선을 연결해주고 올해에 뒤 바뀐 순위를 기반으로 간선의 방향을 바꿔준다. 이후 위상정렬을 해주면 되는데 이 때 큐에 동시에 2개가 들어간다면 ?를 출력하고 n번을 돌리기전에 큐가 비어버린다면 사이클이 생긴것이므로 IMPOSSIBLE을 출력 해 주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172#include #include #.. 더보기
BOJ)2637 장난감조립 문제:icpc.me/2637 장난감 완제품 N을 만드는데 필요한 기본 부품의 종류와 수를 출력하는 문제이다. 여기 기본 부품은 indegree의 수가 0인 정점들이 되고 위상정렬 순서대로 부품의 개수를 중첩 시켜 나가면 답을 구할 수 있다. a[x][y]가 의미하는건 x번 부품(제품)을 만드는데 필요한 기본 부품 y의 개수이다. 123456789101112131415161718192021222324252627282930313233343536373839#include #include #include #include using namespace std;int n, m, a[101][101], in[101], x, y, z;vector vt;int main() { scanf("%d%d", &n, &m); vt.. 더보기

티스토리툴바