[백준 1976번] 여행 가자 https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 2023.04.11 - [코딩 테스트/개념] - Union-Find # 1 코딩 테스트/백준 2023.04.15
Union-Find 🔰 개념 그래프에 사이클이 생성되는지 판별하는 알고리즘이다. union 연산 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 연산이다. 노드 a, b가 각각 A, B 집합에 속 때, union(a, b) = A ∪ B 다. find 연산 두 노드가 같은 집합에 속해 있는지를 확인하는 연산이다. 자신의 대표 노드를 찾아준다. 노드 a가 집합 A에 속할 때, find(a)는 A 집합의 대표 노드를 반환한다. 단순히 대표 노드를 찾는 역할만 하는 것이 아니라, 그래프를 정돈하고 시간 복잡도를 향상시킨다. 🔰원리 초기화: 일반적으로 대표 노드를 저장하는 1차원 배열을 이용한다. 처음에는 노드가 연결되어 있지 않으므로 각 노드가 모두 대표 노드다. 따라서 배열을 자신의 인덱스값으로 초기화한다.. 코딩 테스트/개념 2023.04.11
