🔎 개념
서로소 집합 알고리즘 영상 참고
- 서로소 관계의 집합이란 공통 원소가 없는 두 집합을 뜻함
- 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리
- 트리를 이용해 집합 표현
- 서로 연결된 두 노드(A,B)에서 각각의 루트 노드 A',B' 찾기
- A'를 B'의 루트노드로 설정
- 반복
-> 각 노드의 최종 루트노드가 같은지 여부에 따라 특정 루트노드의 집합에 속하는지 확인
- 반복
import java.util.Scanner;
public class Java0716_1 {
// 노드 수 v, 간선 수 e
public static int v,e;
public static int[] parent = new int[100001];
// 최대 노드 수 100,000개로 가정
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
v = sc.nextInt();
e = sc.nextInt();
// 부모테이블 상에서, 루트노드를 일단 자기 자신으로 초기화
for(int i=0;i<=v;i++) parent[i] =i;
for(int i=0;i<e;i++) {
int a= sc.nextInt();
int b = sc.nextInt();
unionParent(a,b);
}
// 각 원소가 속한 집합(최종 루트노드) 출력하기
System.out.print("각 원소가 속한 집합: ");
for (int i = 1; i <= v; i++) {
System.out.print(findParent(i) + " ");
}
System.out.println();
// 부모 테이블 내용 출력하기
System.out.print("부모 테이블: ");
for (int i = 1; i <= v; i++) {
System.out.print(parent[i] + " ");
}
System.out.println();
}
// 두 원소가 속한 집합을 합치기
public static void unionParent(int a, int b) {
a = findParent(a);
b = findParent(b);
if(a>b) parent[a] = b;
else parent[b] = a;
}
// 특정 원소가 속한 집합(최종 루트노드)를 찾기
public static int findParent(int x) {
if(x == parent[x]) return x;
// 루트노드는 부모테이블 값이 자기 자신과 동일함.(main에서 초기화함)
// 루트노드가 아니라면, 루트노드를 찾을 때까지 재귀
return parent[x] = findParent(parent[x]);
// 최종 루트노드를 parent[x] 에 저장함과 동시에 리턴
}
}서로소 집합을 활용한 사이클 판별
- 무방향 그래프 내에서의 사이클 판별시 가능 ( 방향 그래프는 DFS 이용 )
- 각 간선을 하나씩 확인하며 두 노드의 루트노드 확인
- 루트노드가 서로 같다면 사이클 발생 / 다르다면 두 노드에 대해 합집합 연산 수행
- 반복
// 사이클이 발생하면 종료하는 로직
import java.util.Scanner;
public class Java0716_2 {
public static int v,e;
public static int[] parent = new int[100001];
public static void main(String[] args) {
boolean cycle = false;
Scanner sc = new Scanner(System.in);
v= sc.nextInt();
e = sc.nextInt();
for(int i=1;i<=v;i++) parent[i] = i;
for(int i=0;i<e;i++) {
int a = sc.nextInt();
int b = sc.nextInt();
// 루트노드가 같다면, 즉 집합이 같다면 종료
if(findParent(a) == findParent(b)) {
cycle = true;
break;
}else unionParent(a,b); // 아니면 합집합 수행
if(cycle) System.out.print("사이클이 발생했습니다.");
else System.out.print("사이클이 발생하지 않았습니다.");
}
}
public static void unionParent(int a, int b) {
a = findParent(a);
b = findParent(b);
if(a<b) parent[b] = a;
else parent[a] = b;
}
public static int findParent(int x) {
if(x == parent[x]) return x;
return parent[x] = findParent(x);
}
}
크루스칼 알고리즘(최소 신장 트리)
- 최소한의 비용으로 그래프의 모든 노드들을 거쳐가는 알고리즘
- 사이클이 없어야함. 따라서 각 노드의 최종 루트노드는 단 하나임
- 간선 데이터를 비용을 기준으로 오름차순 정렬
- 간선을 하나씩 확인하여 현재의 간선이 사이클을 발생시키지 않아야 집합에 포함 ( 두 노드의 최종 루트노드가 달라야 함)
- 반복
import java.util.*;
// 두 노드 a,b와 그 사이 거리를 동시에 저장,접근하기 위해 클래스 생성
class Edge implements Comparable<Edge>{
public Edge(int a, int b, int cost) {
this.aNode = a;
this.bNode = b;
this.cost = cost;
}
public int getaNode() {
return this.aNode;
}
public int getbNode() {
return this.bNode;
}
public int getCost() {
return this.cost;
}
private int aNode,bNode,cost;
// 비용 오름차순 정렬
@Override
public int compareTo(Edge o) {
return this.cost - o.cost;
}
}
public class Java0716_3 {
public static int v,e;
public static int[] parent = new int[100001];
public static ArrayList<Edge> edges = new ArrayList<Edge>();
public static int answer =0;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
v = sc.nextInt();
e = sc.nextInt();
for(int i=1;i<=v;i++) parent[i] = i;
for(int i=0;i<e;i++) {
int a = sc.nextInt();
int b = sc.nextInt();
int cost = sc.nextInt();
edges.add(new Edge(a,b,cost));
}
// 간선을 비용 기준으로 정렬
Collections.sort(edges);
for(int i=0;i<edges.size();i++) {
int cost = edges.get(i).getCost();
int a = edges.get(i).getaNode();
int b = edges.get(i).getbNode();
// 사이클이 발생하지 않는 경우에만 집합에 포합시킴
if(findParent(a) != findParent(b)){
unionParent(a,b);
answer += cost;
}
}
System.out.print(answer);
}
public static void unionParent(int a, int b) {
a = findParent(a);
b = findParent(b);
if(a<b) parent[b] =a;
else parent[a] = b;
}
private static int findParent(int x) {
if(x == parent[x]) return x;
return parent[x] = findParent(parent[x]);
}
}위상 정렬
- 사이클이 없는 방향 그래프의 노드를 방향에 거스르지 않게 순서대로 나열
- BFS와 큐를 활용
- 진입차수가 0인 노드를 큐에 넣기
- 1에서 넣은 노드를 다시꺼내 해당 노드에서 나가는 간선을 그래프에서 제거
- 2의 과정으로 인해 진입차수가 0이 된 노드를 큐에 넣기
- 큐가 빌 때까지 반복
--> 각 노드가 큐에 들어온 순서가 곧 위상정렬 수행한 결과!
- 큐가 빌 때까지 반복
❗❗ 주의) 다익스트라 알고리즘의 graph와 비교
- 다익스트라의 간선 : graph.get(a).add(new Node(b,cost)) // a -> b, 비용은 cost
- 위상정렬의 간선 : graph.get(a).add(b) // a -> b, b의 진입차수 +1
package ThisIsCodingTest;
import java.util.*;
public class Java0716_4 {
public static int v,e;
public static int[] indegree = new int[100001];
// 각 노드에 연결된 간선 정보를 담기 위한 그래프 초기화
// 한 노드에 여러개의 선수 노드가 연결될 수 있으니 2차원으로 생성
public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
v = sc.nextInt();
e = sc.nextInt();
for(int i=0;i<=v;i++) graph.add(new ArrayList<Integer>());
for(int i=0;i<e;i++) {
int a = sc.nextInt(); // 선수 노드
int b = sc.nextInt();
graph.get(a).add(b); // a -> b 간선
indegree[b]++; // 진입차수 1 증가
}
topologySort(); // 위상정렬 함수
}
public static void topologySort() {
// 위상정렬 결과를 담을 리스트
ArrayList<Integer> answer = new ArrayList<>();
Queue<Integer> q = new LinkedList<>();
for(int i=1;i<=v;i++) {
// 진입차수가 0이면 큐에 넣기( 처음엔 진입차수가 0인 노드는 하나뿐)
if(indegree[i] == 0) q.offer(i);
}
while(!q.isEmpty()) {
int now = q.poll();
answer.add(now);
// 해당 노드와 연결된 노드들의 진입차수에서 1빼기
for(int i=0; i<graph.get(now).size();i++) {
indegree[graph.get(now).get(i)]--;
if(indegree[graph.get(now).get(i)] ==0)
q.offer(graph.get(now).get(i));
}
}
// 위상 정렬을 수행한 결과 출력
for (int i = 0; i < answer.size(); i++) {
System.out.print(answer.get(i) + " ");
}
}
}📚 팀 결성 - 서로소 집합 알고리즘
import java.util.Scanner;
public class Java0716_5 {
public static int n,m;
public static int[] parent = new int[100001];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
for(int i=1;i<=n;i++) parent[i] = i;
for(int i=0;i<m;i++) {
int x = sc.nextInt();
int a = sc.nextInt();
int b = sc.nextInt();
if(x==0) unionParent(a,b);
else {
int findA = findParent(a);
int findB = findParent(b);
if (findA ==findB) System.out.println("YES");
else System.out.println("NO");
}
}
}
public static int findParent(int x) {
if(x == parent[x] ) return x;
return parent[x] = findParent(parent[x]);
}
private static void unionParent(int a, int b) {
a = findParent(a);
b = findParent(b);
if(a<b) parent[b] = a;
else parent[a] = b;
}
}📚 도시 분할 계획 - 크루스칼 알고리즘
// 도시 분할 계획
// 한 길로 연결된 모든 집을 두 개의 마을로 분리하기위해
// 집합에서 가장 비용이 많이 드는 간선 하나 빼기
import java.util.*;
class Edge implements Comparable<Edge>{
private int cost,nodeA,nodeB;
public Edge(int a,int b,int cost) {
this.cost = cost;
this.nodeA = a;
this.nodeB = b;
}
public int getNodeA() {
return this.nodeA;
}
public int getNodeB() {
return this.nodeB;
}
public int getCost() {
return this.cost;
}
@Override
public int compareTo(Edge o) {
return this.cost - o.cost;
// 아래코드로 하면 에러 발생,,
// if(this.cost < o.cost) return -1;
// return 1;
}
}
public class Java0716_6 {
public static int n,m;
public static int[] parent = new int[100001];
public static ArrayList<Edge> edges = new ArrayList<Edge>();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n=sc.nextInt();
m = sc.nextInt();
for(int i=1;i<=n;i++) parent[i] = i;
for(int i=0;i<m;i++) {
int a = sc.nextInt();
int b = sc.nextInt();
int cost = sc.nextInt();
edges.add(new Edge(a,b,cost));
}
Collections.sort(edges);
int answer =0;
int last = 0; // 집합에 포함되는 간선 중 가장 비용이 큰 간선
for(int i=0;i<edges.size();i++) {
int a = edges.get(i).getNodeA();
int b = edges.get(i).getNodeB();
int cost = edges.get(i).getCost();
if (findParent(a) != findParent(b)) {
unionParent(a,b);
answer+=cost;
last = cost;
// 마지막 간선의 비용 저장
}
}
System.out.print(answer - last);
}
public static void unionParent(int a, int b) {
a = findParent(a);
b = findParent(b);
if(a<b) parent[b] =a;
else parent[a] =b;
}
public static int findParent(int x) {
if(x == parent[x]) return x;
return parent[x] = findParent(parent[x]);
}
}
📚 커리큘럼 - 위상 정렬
주의) 문제가 "최소 시간"을 구하는 것이므로 min()을 써야 겠다고 생각할 수 있다. 하지만 여러개의 선수강의가 있을 수 있고, 그 선수 강의들을 모두 들어야 한다는 점에서 강의 시간이 더 오래 걸리는 경우를 찾는다면, max()로 결과 테이블을 갱신해줘야 한다!
❓ graph.get(nowIdx).get(i) 가 graph.get(nowIdx)노드의 진입 노드 중 하나라고 생각했는데 이때까지 잘못 이해했다.
❗ graph.get(nowIdx)노드가 선수과목이고(시작 노드) graph.get(nowIdx).get(i)가 그 뒤에 연결된 노드 중에 하나다!
graph.get(x).add(i); // 주의) x -> i 방향!
import java.util.*;
public class Java0717_1 {
public static int n;
public static int[] indegree = new int[501]; // new int[n+1]로 하면 인덱스 에러 발생
public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
public static int[] times = new int[501]; // 각 강의번호의 고유 강의 시간
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
for(int i=0; i<=n;i++)
graph.add(new ArrayList<Integer>());
// 입력 10 1 2 -1 이면 10:강의 시간/ 1,2: 이 과목의 선수 과목
for(int i=1;i<=n;i++) { // i = 강의 번호
int a = sc.nextInt(); // 강의 시간
times[i] = a;
while(true){
int x = sc.nextInt(); // 선수 과목 or -1
if(x!=-1) {
graph.get(x).add(i);
// 주의) x -> i 방향!
indegree[i]++;
}else break;
}
}
topologySort();
}
public static void topologySort() {
Queue<Integer> q = new LinkedList<>();
int[] answer = new int[501]; // 각 강의당 선수과목을 거쳐 합한 시간
for(int i=1;i<=n;i++) answer[i] = times[i];
// 처음 시작할 땐 진입차수가 0인 노드 삽입
for(int i=1; i<=n; i++) {
if( indegree[i] == 0) q.offer(i);
}
while(!q.isEmpty()) {
int nowIdx = q.poll();
for(int i=0;i<graph.get(nowIdx).size();i++) {
indegree[graph.get(nowIdx).get(i)]--;
int result = answer[graph.get(nowIdx).get(i)];
result = Math.max(result, answer[nowIdx] + times[graph.get(nowIdx).get(i)]);
answer[graph.get(nowIdx).get(i)] = result;
if(indegree[graph.get(nowIdx).get(i)] == 0)
q.offer(graph.get(nowIdx).get(i));
}
}
for(int i=1;i<=n;i++) System.out.println(answer[i]);
}
}