서로소 집합(Union-find), 크루스칼 알고리즘(최소 신장 트리), 위상 정렬과 관련한 문제들이다. 각 알고리즘의 설명 및 구현은 따로 올릴 것이다.
팀 결성
팀 합치기, 같은 팀 여부 확인 연산을 하는 문제로 Union-Find 방법을 이용해 푸는 문제였다. 0번 연산이 union을 만드는 연산, 1번 연산이 같은 parent를 가지는지 확인하는 연산이었다. 각각에 대해 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
*/
도시 분할 계획
그래프의 최소 신장 트리를 구하고 최소 신장 트리를 구성하는 간선들의 합(-최대 간선)을 구하는 문제였다. 그래프의 간선 정보를 입력받고 간선을 정렬해준 후에 크루스칼 알고리즘으로 최소 신장 트리를 만들고 마지막에 추가된 간선 길이만 빼주면 답을 얻을 수 있다.
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
