유니온파인드

https://www.acmicpc.net/problem/4803 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net 풀이과정 기본 문제인 것 같았지만, 생각해야 될 것이 많았던 문제이다. 입력을 받고 나서, 두 노드의 부모가 다른 집합일 때와 같은 집합일 때로 나눈다. 다른 집합일 때는 부모의 노드를 통일시켜주고, 만약에 두 부모 중 한 집합이라도 사이클이 존재한다면 두 집합 모두 사이클로 변경해준다. 같은 집합일 때는 시작 노드를 사이클로 변경해준다. 만약 사이클이 존재한다면 넘어가주고, 사..

https://www.acmicpc.net/problem/15809 15809번: 전국시대 첫 번째 줄에 국가의 수를 나타내는 N과 기록의 수 M이 주어진다. (1 ≤ N, M ≤ 100,000) 두 번째 줄 부터 N개의 줄에 걸쳐 i번째 국가의 병력 Ai (1 ≤ i ≤ N)가 자연수로 주어진다. (1 ≤ Ai ≤ 10,000) 다 www.acmicpc.net 풀이과정 #include #include #include using namespace std; int N, M, op, P, Q; int parent[100001], res[100001]; int getParent(int x) { if (parent[x] == x) return x; return parent[x] = getParent(parent..

https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 풀이과정 이 문제는 이분 탐색, BFS, 유니온 파인드 3개의 알고리즘이 섞인 문제여서 매우 어려웠던 문제이다. #include #include #include #include #include using namespace std; int n, m, A, B, cost, s, e; bool c[10001]; vector v[10001]; b..

https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 풀이과정 이 문제는 유니온 파인드와 map 알고리즘이 섞인 문제이다. 유니온 파인드 알고리즘을 하려면, 처음에 parent 배열에 각자 자신의 번호로 초기화시켜준다. 한 줄에 2명씩 입력되므로 최대 노드 개수는 2 * F 개가 된다. 입력을 받을 때, 만약 map.count가 0이라면 idx를 넣어주고 1씩 플러스 해준다. 그다음 unionParent 함수를 실행하고, 다른 집합일 경우..

https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 풀이과정 bool 함수의 장점을 느꼈던 문제이다. #include #include #include using namespace std; int n, m, x, y; int parent[500001]; // 부모 노드를 찾는 함수 int getParent(int x) { if (parent[x] == x) return x; return parent[x] = getParent(parent[x])..

https://www.acmicpc.net/problem/16562 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10, www.acmicpc.net 풀이과정 연결되어 있는 노드들 중에 친구비가 작은 친구가 있다면 부모 노드를 바꿔준다. #include #include #include using namespace std; int N, M, k, v, w; int f[10001], parent[10001]; // 부모 노드를 찾는 함수 int getParent(int x) { i..

https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 풀이과정 1이면 도시들이 연결된 것을 의미하므로 unionParent(i, j) 함수를 실행시켜준다. 그럼 연결된 도시들은 가장 작은 부모 노드를 가지고 있을 것이다. 여행 계획에 있는 도시들을 두 개씩 findParent에 넣어보고 만약에 다른 것이 있다면 연결되지 않은 도시라는 뜻이므로 res를 false로 변경한다. #include #include #include using namespace..