Sims의 문제해결 저장소

https://www.acmicpc.net/problem/4195 Union-Find는 크게 두가지 테스크를 진행 할 수 있다고 언급을 했다.1. Cycle 여부 확인2. 동일 그래프 소속 여부 크게 두가지를 알 수 있는데 지난번 테스크는 사이클 여부를 체크하는 문제를 풀어봤다.이번에는 동일 그래프에 속하는지 판단 + @로 조금 다른 find를 하는 문제이다. 이번 알고리즘은 두 사람의 이름이 "A B"와 같이 주어지면, A와 B는 친구 네트워크가 생성된다는 의미이다.이렇게 되면 단순하게 노드를 연결하는 방법(Union)이 된다. 즉, Union 방식으로 그래프를 생성해 나가면 된다. 하지만 한가지 다른점은 Find가 친구관계가 input으로 들어왔을때, 해당 그래프는 몇명의 친구와 연관이 있는지 바로바..

지난번 유니온파인드 개념에 대해 알아보았다. 각 노드들을 병합시켜 가리키고 있는 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과 ..