https://www.acmicpc.net/problem/7511 7511번: 소셜 네트워킹 어플리케이션 각 테스트 케이스마다 "Scenario i:"를 출력한다. i는 테스트 케이스 번호이며, 1부터 시작한다. 그 다음, 각각의 쌍마다 두 사람을 연결하는 경로가 있으면 1, 없으면 0을 출력한다. 각 테스트 케이스 www.acmicpc.net 풀이 기존 bfs 알고리즘을 사용할 시에 시간초과가 일어난다. 주어지는 유저의 수가 n^6까지 주어지기 때문이다. 그래서 분리 집합 알고리즘을 이용해서 답을 구해주었습니다. bfs를 사용하게 되면 확인해야하는 친구 관계의 개수만큼 bfs가 돌아가기에 매우 비효율적입니다. 그러나 분리집합을 사용하게 되면 연결된 최상위 노드만이 저장된 리스트를 비교함으로 효율적으로 ..

https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 풀이 사이클이 생기는지에 대해서 확인해보는 문제. - BFS는 간선을 추가한 그래프를 처음부터 계속 탐색해야하기에 부담이 크다. - 분리 집합을 사용해서 사이클이 생기는지 확인하도록 했다. 분리집합 알고리즘 https://sunghyun98.tistory.com/256 [알고리즘] 분리 집합 분리 집합(Disjoint Set, Union-Find)은 많은 알고리즘 코딩 테스트에서 중요한 자료..