위상 정렬 썸네일형 리스트형 UVaOJ)12645 Water Supply 문제: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4393 오염된 물을 정화하기 위해서 단방향 그래프에서 0번 정점에서 나오는 정화제를 x개의 간선을 추가하여 모든 정점에 뿌려야할 때 연결해야하는 간선 x개의 최솟값을 구하는 문제이다. 이 문제는 정점들을 scc로 묶어준다음 위상정렬을 통하여 해결가능하다. 즉 0번 정점을 포함한 scc를 제외한 indegree가 0인 scc의 개수를 출력해주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545.. 더보기 BOJ)2056 작업 문제: icpc.me/2056 a번 작업을 실행할 때 선행되야 되는 작업 b의 셋이 주어질 때 모든 작업을 완료하는데 걸리는 시간을 출력하는 문제이다. 문제에서 선행관계는 항상 번호가 증가하는 순서로 이루어진다고 하였으므로 사이클이 존재하지 않는 DAG임을 알 수 있다. 따라서 우리는 위상정렬을 해준 뒤 위상정렬의 순서대로 일을 처리해주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142#include #include #include using namespace std;int n, in[10002], c[10002], x, y, r;vector vt;int main() { scanf("%d", &n); vt.re.. 더보기 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.. 더보기 BOJ)9470 Strahler 순서 문제: icpc.me/9470 indegree가 0인 노드들의 순서가 1인데 어떤 노드의 indegree와 연결된 노드 중 순서가 가장 큰 값을 i라고할 때 i가 1개 들어오면 해당 노드의 순서는 i 2개 이상 들어온다면 해당 노드의 순서는 i+1이 된다. 우리는 indegree의 정보를 이용하여 위상정렬을 실행하는데 이때 들어오는 indegree의 최댓값과 개수만 count해주어 값을 갱신해주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include #include #include #include #include using namespace std;int k, m, p,.. 더보기 Topological Sort(위상 정렬) DAG에서 방향성을 거스르지 않게 정점들을 나열하는 알고리즘을 Topological sort(위상 정렬)이라 합니다. DAG란 Directed Acyclic Graph의 줄임말로 직역하자면 사이클이없는 방향(유향) 그래프 정도가 될 것입니다. DAG는 유향 그래프에서 정의되며 DAG가 되려면 Cycle이 없어야 합니다. 우리는 유향 그래프에서 한 정점에서 DFS를 실행 할 경우 DFS의 방문순서에 따라서 스패닝 트리를 얻을 수 있습니다. 우리는 이러한 트리를 DFS 스패닝 트리(DFS Spanning Tree)라고 부르며 DFS 스패닝 트리에서 간선의 특징에 따라 간선 분류를 할 수 있습니다. 1. 트리 간선-> 스패닝 트리에 포함된 간선 2. 순방향 간선-> 스패닝 트리에는 포함되지 않았지만 선조에서 .. 더보기 BOJ)1766 문제집 문제: icpc.me/1766 문제집을 푸는 순서가 주어지는데 이때 가능하면 쉬운 문제부터 풀어야 할 경우 문제를 푸는 순서를 출력하는 문제이다. 우리는 문제집을 푸는 순서가 주어질 때 topological sort를 통하여 순서를 출력할 수 있다. 하지만 가능하면 쉬운 문제를 풀어야 하니 topology가 여러개일 경우 작은 순서를 먼저 출력해줘야 한다. 이는 min heap을 통하여 해결 가능하다. 123456789101112131415161718192021222324252627282930313233#include #include #include #include #define MAX_N 32000using namespace std;int n, m, a, b, in[MAX_N + 1];vector vt.. 더보기 BOJ)2623 음악프로그램 문제: icpc.me/2623 음악프로그램의 출연 순서의 리스트가 주어졌을 때 모든 리스트를 만족시키도록 출연 순서를 출력하는 문제이다. 만약 모든 리스트를 만족할 수 없는 경우 0을 출력하면 된다. 우리는 출연 순서가 A->B->C 라면 A->B / B->C의 방향으로 간선을 연결해 준 뒤 topology를 구해줌으로서 리스트를 구할 수 있다. 이때 모든 리스트를 만족할 수 없는 경우는 사이클이 생기는 경우로서 그래프의 사이클 여부를 체크해줌으로서 확인 가능하다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#include #include #include #include #define MA.. 더보기 BOJ)2252 줄 세우기 문제: icpc.me/2252 N명이 학생이 주어지고 두 학생의 키를 비교한 M개의 정보가 주어질 때 줄을 세운 결과를 출력하는 문제이다. 우리는 두 학생의 우선관계를 방향 그래프를 이용하여 설정해준 뒤 topology를 구해주면 된다. 즉 DFS를 돌리면서 먼저 끝나는 순서대로 스택에 저장해준 뒤 하나씩 뽑으면서 출력해주면 답을 얻을 수 있다. 1234567891011121314151617181920212223242526272829303132333435#include #include #include #include #define MAX_N 32000using namespace std;vector vt;stack st;int n, m, x, y, visited[MAX_N + 1];void dfs(int .. 더보기 이전 1 다음
