#include <cstdio>
#include <queue>
#include <vector>
/**
* https://www.acmicpc.net/problem/2623
* BOJ 백준온라인져지 2623 음악프로그램 풀이
*/
using namespace std;
int main () {
int numberOfVector;
int testCase;
scanf("%d%d", &numberOfVector, &testCase);
numberOfVector++;
int *indegree = new int[numberOfVector];
vector<vector<int> > edges;
edges.resize(numberOfVector);
for (int i = 1; i < numberOfVector; i++) {
indegree[i] = 0;
}
while(testCase--) {
int numberOfEdge;
int firstSinger;
scanf("%d%d", &numberOfEdge, &firstSinger);
for (int i = 1; i < numberOfEdge; i++) {
int lastSinger;
scanf("%d", &lastSinger);
indegree[lastSinger]++;
edges[firstSinger].push_back(lastSinger);
firstSinger = lastSinger;
}
}
queue<int> result;
queue<int> queue;
for (int i = 1; i < numberOfVector; i++) {
if (indegree[i] == 0) queue.push(i);
}
while (queue.size()) {
int here = queue.front();
queue.pop();
result.push(here);
for (int i = 0, size = edges[here].size(); i < size; i++) {
int there = edges[here][i];
indegree[there]--;
if (indegree[there] == 0) queue.push(there);
}
}
if(result.size() == numberOfVector - 1) {
while(result.size()) {
printf("%d\n", result.front());
result.pop();
}
} else {
printf("0");
}
}
view raw BOJ_2623.cpp hosted with ❤ by GitHub

위상 정렬 Week 끝!


내일은 Merge Sort 를 다시 복습 해야겠다.


다음주는 MST 를 공부해야지!

저작자표시

'IT > 알고리즘' 카테고리의 다른 글

BOJ 백준온라인져지 1927 최소 힙 풀이  (0) 2017.12.28
BOJ 백준온라인져지 14927 전구 끄기 풀이  (0) 2017.12.26
애니팡같은 게임  (0) 2017.12.21
BOJ 백준온라인져지 1766 문제집 풀이  (0) 2017.12.21
BOJ 백준온라인져지 1005 ACM Craft 풀이  (0) 2017.12.19

ACM CRAFT와 비슷한 문제다.

1. in-degree가 0인거 부터

2. 문제 번호가 낮은거 우선순위


문제 번호가 낮은거 우선순위는 priority_queue로 하면되고,

in-degree는 위상정렬



#include <cstdio>
#include <queue>
#include <vector>
/**
* https://www.acmicpc.net/problem/1766
* BOJ 백준온라인져지 1766 문제집 풀이
*/
using namespace std;
int main () {
int numberOfVector;
int numberOfEdge;
scanf("%d%d", &numberOfVector, &numberOfEdge);
numberOfVector++;
numberOfEdge++;
int *indegree = new int[numberOfVector];
vector<vector<int> > edges;
edges.resize(numberOfVector);
for (int i = 1; i < numberOfVector; i++) {
indegree[i] = 0;
}
for (int i = 1; i < numberOfEdge; i++) {
int firstSolve;
int lastSolve;
scanf("%d%d", &firstSolve, &lastSolve);
edges[firstSolve].push_back(lastSolve);
indegree[lastSolve]++;
}
priority_queue<int, vector<int>, greater<int> > queue;
for (int i = 1; i < numberOfVector; i++) {
if (indegree[i] == 0) queue.push(i);
}
while (queue.size()) {
int here = queue.top();
queue.pop();
printf("%d\n", here);
for (int i = 0, size = edges[here].size(); i < size; i++) {
int there = edges[here][i];
indegree[there]--;
if (indegree[there] == 0) queue.push(there);
}
}
}
view raw BOJ_1766.cpp hosted with ❤ by GitHub
저작자표시

'IT > 알고리즘' 카테고리의 다른 글

BOJ 백준온라인져지 2623 음악프로그램 풀이  (0) 2017.12.23
애니팡같은 게임  (0) 2017.12.21
BOJ 백준온라인져지 1005 ACM Craft 풀이  (0) 2017.12.19
BOJ 백준온라인져지 14926 Not Equal 풀이  (0) 2017.12.17
BOJ 백준온라인져지 14925 목장 건설하기 풀이  (0) 2017.12.16

A -> B

C -> B 일때,


B = MAX(A, C)

이런식으로 값이 들어간다.



이번주는 위상 정렬 문제만 풀어야지 ㅋㅋ


만약 진입차수가 0인게 endVertex 인 것을 처리하기 위해

if(indegree[i] == 0) queue.push(i), minimumSecond[i] = second[i];


#include <cstdio>
#include <queue>
#include <vector>
/**
* https://www.acmicpc.net/problem/1005
* BOJ 백준온라인져지 1005 ACM Craft 풀이
*/
int max(int a, int b) {
return a > b ? a : b;
}
using namespace std;
int main() {
int testCase;
scanf("%d", &testCase);
while(testCase--) {
int numberOfVertex;
int numberOfEdge;
scanf("%d%d", &numberOfVertex, &numberOfEdge);
numberOfVertex++;
int *minimumSecond = new int[numberOfVertex];
int *second = new int[numberOfVertex];
int *indegree = new int[numberOfVertex];
for(int i = 1; i < numberOfVertex; i++) {
indegree[i] = second[i] = minimumSecond[i] = 0;
scanf("%d", &second[i]);
}
queue<int> queue;
vector<vector<int> > vector;
vector.resize(numberOfVertex);
for(int i = 0; i < numberOfEdge; i++) {
int startVertex;
int endVertex;
scanf("%d%d", &startVertex, &endVertex);
vector[startVertex].push_back(endVertex);
indegree[endVertex]++;
}
for(int i = 1; i < numberOfVertex; i++) {
if(indegree[i] == 0) queue.push(i), minimumSecond[i] = second[i];
}
int endVertex;
scanf("%d", &endVertex);
while(queue.size()) {
int cur = queue.front();
queue.pop();
for(int i = 0, size = vector[cur].size(); i < size; i++) {
int next = vector[cur][i];
indegree[next]--;
minimumSecond[next] = max(minimumSecond[next], minimumSecond[cur] + second[next]);
if(indegree[next] == 0) queue.push(next);
}
}
printf("%d\n", minimumSecond[endVertex]);
}
}
view raw BOJ_1005.cpp hosted with ❤ by GitHub
저작자표시

'IT > 알고리즘' 카테고리의 다른 글

애니팡같은 게임  (0) 2017.12.21
BOJ 백준온라인져지 1766 문제집 풀이  (0) 2017.12.21
BOJ 백준온라인져지 14926 Not Equal 풀이  (0) 2017.12.17
BOJ 백준온라인져지 14925 목장 건설하기 풀이  (0) 2017.12.16
BOJ 백준온라인져지 14924 폰 노이만과 파리 풀이  (0) 2017.12.16

+ Recent posts

티스토리툴바