Algorithem/백준 PS with code
백준 #20040 - [G4] 사이클 게임 : 그래프사이클, 유니온파인드
https://www.acmicpc.net/problem/20040 (python3) 그래프의 대표 유형중 하나인 사이클 존재 유무 탐색 문제입니다. 그래프 사이클 탐색의 경우 유니온 파인드 알고리즘으로 해결할 수 있습니다. 유니온 파인드 이어진 점들을 하나의 그룹으로 표현하는 방식입니다. 가장 직관적인 접근으로는 그룹 A와 B가 합쳐지는 경우 이렇게 모든 점들을 탐색하면서 A 를 B 로 편입시키는 방법입니다. 다만 이 방법을 사용하게 되면 새로운 선이 하나 추가될때 마다 모든 점의 그룹 상태를 모두 확인하여 바꿔야하기에 점이 많아질수록 연산 부담이 커집니다. 이 연산을 획기적으로 줄이는 방식이 union find 가 되겠습니다. 핵심 아이디어는 각 점은 자신의 부모 노드만 저장하고 있고, 필요시마다 해..
