문제) 백준 - 분리 집합 - 사이클 게임
https://www.acmicpc.net/problem/20040
20040번: 사이클 게임
사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한
www.acmicpc.net
분리 집합을 이용하여 쉽게 풀 수 있는 문제. 선분을 그리면 같은 집합으로 merge하고 parent가 같을 경우 사이클이 있는 것으로 간주한다.
C++ 소스 코드)
ps. 사이클에 꽂혀서 dfs만 주구장창 생각했다...
반응형
'PS(Problem Solving) > 백준_BOJ' 카테고리의 다른 글
| [백준] 2056번 - 작업 (C++) 문제 및 풀이 (0) | 2021.10.01 |
|---|---|
| [백준] 4811번 - 알약 (C++) 문제 및 풀이 (0) | 2021.09.29 |
| [백준] 11653번 - 소인수 분해 (C++) 문제 및 풀이 (0) | 2021.09.27 |
| [백준] 14881번 - 물통 문제 (C++) 문제 및 풀이 (0) | 2021.09.24 |
| [백준] 1972번 - 놀라운 문자열 (C++) 문제 및 풀이 (0) | 2021.09.23 |
댓글