코린이의 소소한 공부노트

1. Input 1) int n - 그래프의 노드의 개수 - 노드에는 0번부터 n-1번까지의 번호가 붙어 있다. 2) int[][] edges - edges[i] = [u_i, v_i]. u_i번 노드와 v_i번 노드가 연결되어 있다. 3) int source 4) int destination 2. Output 1) 주어진 그래프에서 source에서 destination으로 가는 경로가 있다면 true, 없다면 false를 반환 3. Constraint 1) 1

1. Problem - 크루스칼 알고리즘을 사용하여 모든 노드를 연결하는 최소 비용을 구해보자. - 최소 비용 신장 트리(minimum cost spanning tree)를 만드는 대표적인 알고리즘이다. - 각 노드를 연결하는 간선의 정보(연결된 노드, 비용)를 이용해 간선을 정렬한 후 사이클을 만들지 않게 적은 비용의 간선부터 차례대로 선택해 나간다. - 최소한의 비용으로 모든 노드를 이어야 하기 때문에, 사이클을 만드는 것은 비용 낭비가 된다. - 간선을 선택하기 전에 사이클 테이블을 확인해야 하는데, 이는 이미 연결된 노드인지 알아보기 위함이다. 사이클 테이블은 union-find(합집합 찾기) 알고리즘을 이용한다. 2. Input 1) int[][] graph - 연결된 노드를 표현 2) int[..

1. Problem - 여러 개의 노드 중 2개를 선택했을 때, 두 노드가 같은 그래프에 있는지 알아보자. - 합집합 찾기(union find) 알고리즘은 i번 노드에 대한 부모 노드의 값을 arr[i]에 저장해서 m번 노드와 n번 노드의 부모가 같다면 같은 그래프에 있다고 판단하는 알고리즘이다. - 한 그래프의 노드들을 연결할 때 부모 노드가 여러개가 생긴다면 더 작은 값으로 저장한다. 이 과정을 합침(union) 과정이라 한다. - 합침 과정에서 최종 부모를 찾기 위해 재귀적으로 메서드를 호출하게 된다. - 찾기(find) 과정에서는 두 노드의 부모를 찾아 같은지 확인한다. 2. Input 1) int[][] graph - 연결된 노드를 표현 2) int a, b 3. Output 1) a, b가 같..