Make-set(x)
p[x] ← x
Find-Set(x)
IF x == p[x] : RETURN x
ELSE : RETURN Find-Set(p[x])
Union(x, y)
p[Find-Set(y)] ← Find-Set(x)
Make-Set(x)
p[x] : 노드 x의 부모 저장
rank[x] : 루트 노드가 x인 트리의 랭크 값 저장
Make-set(x)
p[x] ← x
rank[x] ← 0
Find-Set(x) : x를 포함하는 집합을 찾는 연산
Find-Set(x)
IF x != p[x] : // x가 루트가 아닌 경우
p[x] ← Find-Set(p[x])
RETURN p[x]
Union(x, y) : x와 y를 포함하는 두 집합을 통합하는 연산
Union(x, y)
Link(Find-Set(x), Find-Set(y))
Link(x, y)
IF rank[x] > rank[y] :
p[y] ← x
ELSE
p[x] ← y
IF rank[x] == rank[y] :
rank[y]++
KRUSKAL Algorithm : 간선을 하나씩 선택해서 MST를 찾는 알고리즘
최초, 모든 간선을 가중치에 따라 오름차순으로 정렬
가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킴
n-1개의 간선이 선택될 때까지 2를 반복
Pseudo Code
MST-KRUSKAL(G, w)
A ← 0 // 0 : 공집합
FOR vertex v in G.V // G.V : 그래프의 정점 집합
Make-Set(v) // G.E : 그래프의 간선 집합
G.E에 포함된 간선들을 가중치 w에 의해 정렬
FOR 가중치가 가장 낮은 간선 (u, v) ∈ G.E 선택(n-1개)
IF Find-Set(u) ≠ Find-Set(v)
A ← A ∪ {(u, v)}
Union(u, v)
RETURN A;
Code
static int[] arr, p;
static int V, E;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
V = Integer.parseInt(st.nextToken()); // V : 정점의 개수, 0부터 시작
E = Integer.parseInt(st.nextToken()); // E : 간선의 수
arr = new int[V];
// 간선을 저장하기 위해서 클래스를 사용할 수도 있지만
// 배열을 이용해서 저장할 예쩡
// 0 : 시작정점 / 1 : 끝정점 / 2 : 가중치
int[][] edges = new int[E][3];
for (int i = 0; i < E; i++) {
st = new StringTokenizer(br.readLine());
edges[i][0] = Integer.parseInt(st.nextToken());
edges[i][1] = Integer.parseInt(st.nextToken());
edges[i][2] = Integer.parseInt(st.nextToken());
}
// 크루스칼 1단계 : 간선 오름차순으로 정렬
Arrays.sort(edges, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[2] - o2[2];
}
});
// 크루스칼 2단계 : V-1개의 간선을 뽑는데, 사이클이 발생 안하는 녀석들만 선택
p = new int[V];
// make-set
for (int i = 0; i < V; i++) {
makeset(i);
}
int ans = 0; // 최소비용을 저장할 변수
int pick = 0; // 뽑은 간선의 수
// 모든 간선을 순회하면서 체크
for (int i = 0; i < E; i++) {
// i번째의 간선을 뽑아 두 정점의 대표를 확인
int x = edges[i][0];
int y = edges[i][1];
if (findset(x) != findset(y)) {
union(x, y);
ans += edges[i][2];
pick++;
}
if (pick == (V-1)) break;
}
bw.write(ans);
bw.flush();
bw.close();
}
static void makeset(int x) {
p[x] = x;
// Rank 따로 설정 X
}
// 대표를 반환해야 하므로
static int findset(int x) {
// 순수 기술
// if (x == p[x]) return x;
// return findset(p[x]);
// path compression 적용
if (x != p[x]) p[x] = findset(p[x]);
return p[x];
}
static void union(int x, int y) {
p[findset(y)] = findset(x);
// Rank 고려 X, 그냥 무조건 y를 x 밑으로 설정
}
PRIM Algorithm : 하나의 정점에서 연결된 간선들 중에서 하나씩 선택하면서 MST를 만들어 가는 방식
과정
서로소인 2개의 집합 정보를 유지
Code : priority queue를 이용할 수도 있고 반복문을 이용할 수도 있다.
단, 다익스트라 알고리즘에서 pq를 쓸 예정이라 pq를 포함한 걸로 공부하자.
priority queue를 사용한 구현
static boolean[] visited;
static int V, E;
static class Edge implements Comparable<Edge> {
int st, ed, w;
public Edge(int st, int ed, int w) {
this.st = st;
this.ed = ed;
this.w = w;
}
@Override
public int compareTo(Edge o) {
return Integer.compare(this.w, o.w);
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
V = Integer.parseInt(st.nextToken()); // V : 정점의 개수, 0부터 시작
E = Integer.parseInt(st.nextToken()); // E : 간선의 수
List<Edge>[] adjList = new ArrayList[V];
for (int i = 0; i < V; i++) {
adjList[i] = new ArrayList<>();
}
for (int i = 0; i < E; i++) {
st = new StringTokenizer(br.readLine());
int A = Integer.parseInt(st.nextToken()); // 시작 정점
int B = Integer.parseInt(st.nextToken()); // 도착 정점
int W = Integer.parseInt(st.nextToken()); // 가중치
// 무향 그래프이므로
adjList[A].add(new Edge(A, B, W));
adjList[B].add(new Edge(B, A, W));
}
visited = new boolean[V]; // 방문 처리를 위한 용도
PriorityQueue<Edge> pq = new PriorityQueue<>();
// 시작정점을 하나 뽑고 시작
visited[0] = true; // 0번 정점을 기준으로 시작
// 1
// for (int i = 0; i < adjList[0].size(); i++) {
// pq.add(adjList[0].get(i));
// }
//2
// for (Edge e : adjList[0]) {
// pq.add(e);
// }
// 위 두가지 방식과 같은 역할
pq.addAll(adjList[0]);
int pick = 1; // 확보한 정점의 개수
int ans = 0;
// pick < V 일 때 반복
while (pick != V) {
Edge e = pq.poll();
if (visited[e.ed]) continue;
ans += e.w;
pq.addAll(adjList[e.ed]);
visited[e.ed] = true;
pick++;
}
bw.write(ans + "");
bw.flush();
bw.close();
}
반복문을 이용한 구현
static int[][] adjArr;
static int[] p, dist;
static boolean[] visited;
static int V, E, ans;
static final int INF = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
V = Integer.parseInt(st.nextToken()); // V : 정점의 개수, 0부터 시작
E = Integer.parseInt(st.nextToken()); // E : 간선의 수
adjArr = new int[V][V];
for (int i = 0; i < E; i++) {
st = new StringTokenizer(br.readLine());
int A = Integer.parseInt(st.nextToken()); // 시작 정점
int B = Integer.parseInt(st.nextToken()); // 도착 정점
int W = Integer.parseInt(st.nextToken()); // 가중치
// 무향 그래프이므로
adjArr[A][B] = W;
adjArr[B][A] = W;
}
visited = new boolean[V]; // 방문 처리를 위한 용도
p = new int[V]; // 어디에서 왔는지에 대한 정보를 저장하는 용도
dist = new int[V]; // key라고 불리는 가장 작은 값을 저장하는 용도
// dist 배열의 모든 원소를 아주 큰 값으로 갱신
for (int i = 0; i < V; i++) {
dist[i] = INF;
}
// 위와 동일한 역할
// Arrays.fill(dist, INF);
// 임의의 한점을 선택해서 시작
dist[0] = 0; // 0번 정점을 기준으로 시작
p[0] = -1;
ans = 0;
// 정점 개수만큼 반복해도 되지만
// 마지막에는 이미 모든 간선 가중치를 확인했으므로 굳이 필요없다.
// 프림 동작
for (int i = 0; i < V-1; i++) {
// 1. 가장 작은 값을 선택
int min = INF;
int idx = 0;
// 아직 안뽑힌 정점 중 가장 작은 값 선택
for (int j = 0; j < V; j++) {
if (!visited[j] && dist[j] < min) {
min = dist[j];
idx = j;
}
} // idx에는 가장 작은 값을 가지고 있는 정점 번호가 저장
visited[idx] = true; // 선택
// 2. 뽑은 정점을 이용해서 갱신할 수 있는게 있다면 모두 갱신
// 인접 행렬이므로 모든 정점을 확인하는 것
for (int j = 0; j < V; j++) {
if (!visited[j] && adjArr[idx][j] != 0 && dist[j] > adjArr[idx][j]) {
dist[j] = adjArr[idx][j];
p[j] = idx;
}
}
}
for (int i = 0; i < V; i++) {
ans += dist[i];
}
bw.write(ans + "");
bw.flush();
bw.close();
}
DIJKSTRA Algorithm : 시작 정점에서 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식
탐욕 기법을 사용한 알고리즘으로 MST의 프림 알고리즘과 유사
시작 정점(s)에서 끝 정점(t)까지의 최단 경로에 정점 x가 존재한다.
이때, 최단 경로는 s에서 x까지의 최단 경로와 x에서 t까지의 최단 경로로 구성된다.
동작 과정
Code
공통 부분
static final int INF = Integer.MAX_VALUE;
static int V, E;
static List<Node>[] adjList;
static int[] dist;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
V = Integer.parseInt(st.nextToken()); // V : 정점의 개수, 0부터 시작
E = Integer.parseInt(st.nextToken()); // E : 간선의 수
adjList = new ArrayList[V];
for(int i = 0 ; i<V; i++)
adjList[i] = new ArrayList<>();
dist = new int[V];
Arrays.fill(dist, INF);
for (int i = 0; i < E; i++) {
st = new StringTokenizer(br.readLine());
int A = Integer.parseInt(st.nextToken()); // 시작 정점
int B = Integer.parseInt(st.nextToken()); // 도착 정점
int W = Integer.parseInt(st.nextToken()); // 가중치
// 유향 그래프이므로
adjList[A].add(new Node(B, W));
}
dijkstra(0);
bw.write(Arrays.toString(dist));
bw.flush();
bw.close();
}
priority queue를 이용한 구현
static class Node implements Comparable<Node> {
int v, w;
public Node(int v, int w) {
this.v = v;
this.w = w;
}
@Override
public int compareTo(Node o) {
return Integer.compare(this.w, o.w);
}
}
private static void dijkstra(int start) {
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.offer(new Node(start, 0));
dist[start] = 0; // 시작 노드까지의 거리는 0
while (!pq.isEmpty()) {
Node curr = pq.poll();
if (dist[curr.v] < curr.w) continue;
for (int i = 0; i < adjList[curr.v].size(); i++) {
Node next = adjList[curr.v].get(i);
if (dist[next.v] > curr.w + next.w) {
dist[next.v] = curr.w + next.w;
pq.offer(new Node(next.v, dist[next.v]));
}
}
}
}
반복문을 이용한 구현
static class Node {
int v, w;
public Node(int v, int w) {
this.v = v;
this.w = w;
}
}
private static void dijkstra(int start) {
boolean[] visited = new boolean[V];
dist[start] = 0; // 시작 노드까지의 거리는 0
for (int i = 0; i < V-1; i++) {
int min = INF;
int idx = -1;
// 선택하지 않은 정점 중 dist가 가장 짧은 것을 선택
for (int j = 0; j < V; j++) {
if (!visited[j] && min > dist[j]) {
min = dist[j];
idx = j;
}
}
if (idx == -1) break;
visited[idx] = true; // 선택
// 갱신 가능하다면 생신
for (int j = 0; j < adjList[idx].size(); j++) {
Node curr = adjList[idx].get(j);
// 방문하지 않았고, 연결도 되었고(인접행렬일 때 해당),
// 이미 가지고 있는 값보다 더 낮은 값이 있다면 갱신
if (!visited[curr.v] && dist[curr.v] > dist[idx] + curr.w) {
dist[curr.v] = dist[idx] + curr.w;
}
}
}
}
기본 점화식
Code
public static final int INF = (int) 1e9; // 무한을 의미하는 값으로 10억을 설정
// 노드의 개수(N), 간선의 개수(M), 거쳐 갈 노드(X), 최종 목적지 노드(K)
public static int n, m, x, k;
// 2차원 배열(그래프 표현)를 만들기
public static int[][] graph = new int[101][101];
public static void main(String[] args) {
...
// 최단 거리 테이블을 모두 무한으로 초기화
for (int i = 0; i < 101; i++) {
Arrays.fill(graph[i], INF);
}
// 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
for (int a = 1; a <= n; a++) {
for (int b = 1; b <= n; b++) {
if (a == b) graph[a][b] = 0;
}
}
// 각 간선에 대한 정보를 입력 받아, 그 값으로 초기화
for (int i = 0; i < m; i++) {
// A와 B가 서로에게 가는 비용은 1이라고 설정
int a = sc.nextInt();
int b = sc.nextInt();
graph[a][b] = 1;
graph[b][a] = 1;
}
x = sc.nextInt();
k = sc.nextInt();
// 점화식에 따라 플로이드 워셜 알고리즘을 수행
for (int k = 1; k <= n; k++) {
for (int a = 1; a <= n; a++) {
for (int b = 1; b <= n; b++) {
graph[a][b] = Math.min(graph[a][b], graph[a][k] + graph[k][b]);
}
}
}
// 수행된 결과를 출력
int distance = graph[1][k] + graph[k][x];
// 도달할 수 없는 경우, -1을 출력
if (distance >= INF) {
System.out.println(-1);
}
// 도달할 수 있다면, 최단 거리를 출력
else {
System.out.println(distance);
}
}