Sims의 문제해결 저장소

지난번 유니온파인드 개념에 대해 알아보았다. 각 노드들을 병합시켜 가리키고 있는 root-node로 업데이트를 진행시키는 방법이었다.그 후 병합된 정보를 바탕으로 find을 찾아 같은 그래프에 속해있는지, 사이클이 있는지 살펴 볼 수 있다고 하였다. 그럼 적용가능한 문제를 하나 풀어보고자 한다.https://www.acmicpc.net/problem/20040 '백준'사이트에 있는 '사이클 게임' 문제이다.문제를 간단하게 정리해보면, 노드간 간선을 하나씩 그리는 게임을 하게 되는데, 진행하다보면 어느순간에 cycle이 생기는 순간이 생길것이다. 이걸 판단해 줄 수 있는 프로그램을 만들어 달라는 것이다. 정확히 유니온 파인드 알고리즘만 알고 있으면 풀 수 있는 문제다. 이 문제의 핵심은 Find에 존재한다..

알고리즘 Union & Find 알고리즘에 관해서 정리하고자 한다.알고리즘 이름 그래도 합치고, 찾는 알고리즘이다. 대개 이 알고리즘은 노드별 연결이 되어있을때, 사이클이 존재하는가를 찾는데 많이 사용된다.   위 그림처럼 노드와 간선이 존재한다고 했을때, 해당 그래프에서 사이클이 존재하는가 아닌가를 찾아낼 수 있다.사람의 눈으로 보면 간단하게 1->2->5->1의 사이클이 보이지만 알고리즘으로는 어떻게 알게되는지 알아보자.  위와같은 과정을 거쳐 최종적으로는 모든 노드의 root는 1에 연결되어있는 결과를 얻을 수 있다. 천천히 살펴보면 1. (1-2)의 경우, 간선으로 연결되어 있어서 2의 root-node값을 1의 root-node로 바꿔준다.(여기서 1의 root-node로 변경해준 이유는 1과 ..