이들은 union-find, Kruskal의 알고리즘(최소 스패닝 트리) 및 위상 정렬과 관련된 문제입니다.
각 알고리즘의 설명 및 구현은 별도로 게시됩니다.
팀 빌딩
팀을 병합하고 같은 팀인지 확인하는 문제로 Union-Find 방법을 사용하여 풀어야 하는 문제였습니다.
오퍼레이션 0은 유니온을 만드는 오퍼레이션이었고, 오퍼레이션 1은 부모가 같은지 확인하는 오퍼레이션이었습니다.
각각에 대해 makeUnion 및 findParent 작업을 생성하여 문제를 해결했습니다.
int parent(100001) = { 0 };
int find_parent(int a, int b) { //항상 a<b 인 값이 들어온다
if (parent(b) !
= b) { //한 집합 안에 있을수도 있음
parent(b) = find_parent(a, parent(b));
}
return parent(b);
}
void make_union(int a,int b) {
a = find_parent(parent(a), a);
b = find_parent(parent(b), b);
if (a < b) {
parent(b) = a;
}
else parent(a) = b;
}
int main() {
int N, M;
int i;
int oper, a, b;
int compareP, p;
scanf("%d %d", &N, &M);
for (i = 0; i <= M; i++) { //처음에 parent를 자기 자신으로 초기화
parent(i) = i;
}
for (i = 0; i < M; i++) {
scanf("%d %d %d", &oper, &a, &b);
if (oper == 0) {
make_union(a, b);
}
else if (oper == 1) {
if (a < b) {
p = find_parent(a, b); //b의 parent가 p
compareP = a;
}
else {
p = find_parent(b, a); //a의 parent가 p
compareP = b;
}
if (p == compareP) printf("YES\n");
else printf("NO\n");
}
}
}
/*
7 8
0 1 3
1 1 7
0 7 6
1 7 1
0 3 7
0 4 2
0 1 1
1 1 1
*/
지구 계획
문제는 그래프의 최소 스패닝 트리를 구하고 최소 스패닝 트리를 구성하는 에지의 합(-최대 에지)을 찾는 것이었다.
그래프의 에지 정보를 입력하고 에지를 정렬한 후 Kruskal 알고리즘을 사용하여 최소 스패닝 트리를 구성하고 끝에 추가된 에지의 길이를 빼기만 하면 답을 얻을 수 있습니다.
vector<tuple<int, int, int>> edge; //w, a,b -> 간선을 가중치 기준으로 정렬해야 하기 때문
//최소신장트리의 간선이 가중치 순서대로 들어 있고, 가중치를 저장함
//여기에 저장되어 있는 간선만 남기고 나머지 간선은 필요 없음 + treeWeight(N) 또한 필요 없음(그래프를 2개로 나눌 때 가장 비싼 간선을 버리면 됨)
int parent(100001); //각 정점의 부모
void initParent(int N); //parent를 자기 자신으로 초기화
bool isUnion(int a, int b); //a와 b가 같은 그룹인지 확인
void makeUnion(int a, int b); //a와 b를 합치기
int findParent(int a); //a의 부모 찾기
int minTreeSum = 0; //최소신장 트리의 가중치 합 (마지막 가중치 제외)
int lastWeight; //마지막 가중치
void kruskal(int N, int M); //최소 신장 트리 만들기
int main() {
int N, M;
int i;
int A, B, C;
int originSum=0; //맨 처음 그래프의 모든 간선의 가중치 합
scanf("%d %d", &N, &M);
for (i = 0; i < M; i++) {
scanf("%d %d %d", &A, &B, &C);
edge.push_back({ C,A,B });
originSum += C;
}
kruskal(N, M);
printf("%d", minTreeSum - lastWeight);
}
void initParent(int N) {
int i;
for (i = 1; i <= N; i++) {
parent(i) = i;
}
}
bool isUnion(int a, int b) {
int pa, pb;
pa = findParent(a);
pb = findParent(b);
if (pa == pb) return true;
else return false;
}
void makeUnion(int a, int b) {
a = findParent(a);
b = findParent(b);
if (a < b) {
parent(b) = a;
}
else parent(a) = b;
}
int findParent(int a) {
if (parent(a) !
= a) { //상위 조상이 존재함
parent(a) = findParent(parent(a));
}
return parent(a);
}
void kruskal(int N, int M) { //M개의 간선을 하나씩 조사하기 start와 end가 union인지, 아니면 union 만들고 tree에 넣기
int i;
int a, b, w;
//간선 sort 해주기
sort(edge.begin(), edge.end());
//parent 값 초기화
initParent(N);
for (i = 0; i < M; i++) {
w = get<0>(edge(i));
a = get<1>(edge(i));
b = get<2>(edge(i));
if (!
isUnion(a,b)) { //union이 아니면
makeUnion(a, b); //그룹 만들기
minTreeSum += w;
lastWeight = w;
//printf("make i: %d a: %d b: %d w: %d\n",i,a,b,w);
}
}
}
/*
7 12
1 2 3
1 3 2
3 2 1
2 5 2
3 4 4
7 3 6
5 1 5
1 6 2
6 4 1
6 5 3
4 5 3
6 7 4
과정
대표적인 위상 정렬 문제로 각 노드의 시간을 출력하는 문제이다.
진입도가 가장 낮은 노드를 순서대로 검사하여 dist 값을 구합니다.
#define MAX_INT
using namespace std;
vector<int> g(501); //연결된 노드
int time(501) = { 0 };
int in(501) = { 0 }; //각 노드의 진입차수
int dist(501); //결과
int N;
void topology() {
queue<int> q; //진입차수 가장 낮은 노드
int i;
int nowNode;
int nextNode;
for (i = 1; i <= N; i++) { //처음에 진입차수 0인 노드 넣기
if (in(i) == 0) {
q.push(i);
}
dist(i) = time(i);
}
while (!
q.empty()) {
nowNode = q.front();
q.pop();
for (i = 0; i < g(nowNode).size(); i++) {
nextNode = g(nowNode)(i);
//dist 정정
dist(nextNode) = max(dist(nextNode), dist(nowNode) + time(nextNode));
in(nextNode)--;
if (in(nextNode) == 0) { //진입차수 0 되면 q에 push
q.push(nextNode);
}
}
}
}
int main() {
int t, num;
int i;
scanf("%d", &N);
for (i = 1; i <= N; i++) {
scanf("%d", &t);
while (1) {
scanf("%d", &num);
if (num == -1) break;
g(num).push_back(i);
in(i)++;
}
time(i) = t;
}
topology();
for (i = 1; i <= N; i++) {
printf("%d\n", dist(i));
}
}
/*
5
10 -1
10 1 -1
4 1 -1
4 3 1 -1
3 3 -1
*/
http://www.yes24.com/product/goods/91433923