danbibibi
article thumbnail

1. 문제

문제 바로가기> BOJ 20040번: 사이클 게임

 

20040번: 사이클 게임

사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한

www.acmicpc.net

 

2. 풀이

union-find를 이용하여 cycle을 찾아주었다.

<cpp />
#include<iostream> #define MAX 500005 using namespace std; int N, M; int par[MAX]; int find_(int x){ if(par[x] == x) return x; return par[x] = find_(par[x]); } int union_(int y, int x){ int py = find_(y); int px = find_(x); if(py != px) { par[px] = py; return 0; } return 1; } void solve(){ cin >> N >> M; // 1. 초기화 for (int i = 0; i < N; i++) par[i] = i; // 2. cycle 찾기 int ans = 0; for (int m = 1; m <= M; m++){ int y, x; cin >> y >> x; if(union_(y, x)) { ans = m; break; } } cout << ans; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); solve(); }

 

 

처음에 아래와 같이 풀어서 "시간 초과" 가 발생했는데, 불 필요한 find_() 연산이 발생하기 때문인 것 같다.

find_(y) != find_(x) 로 확인하고, union_(y, x) 연산 안에서도 또 재귀적으로 대표 노드를 찾는 find_() 함수를 사용하니까..!

<cpp />
#include<iostream> #define MAX 500005 using namespace std; int N, M; int par[MAX]; int find_(int x){ if(par[x] == x) return x; return par[x] = find_(par[x]); } int union_(int y, int x){ par[find_(x)] = find_(y); } void solve(){ cin >> N >> M; // 1. 초기화 for (int i = 0; i < N; i++) par[i] = i; // 2. cycle 찾기 int ans = 0; for (int m = 1; m <= M; m++){ int y, x; cin >> y >> x; if(find_(y) != find_(x)) { union_(y, x); } else{ ans = m; break; } } cout << ans; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); // freopen("../test/input.txt", "r", stdin); solve(); }

'문제 풀이 > 백준' 카테고리의 다른 글

BOJ 9466번: 텀 프로젝트  (0) 2024.03.26
BOJ 2617번: 구슬 찾기  (0) 2024.03.25
BOJ 3020번: 개똥벌레  (0) 2024.03.20
BOJ 16947번: 서울 지하철 2호선  (1) 2024.03.07
BOJ 5719번: 거의 최단 경로  (0) 2024.02.21
profile

danbibibi

@danbibibi

꿈을 꾸는 시간은 멈춰 있는 것이 아냐 두려워하지 마 멈추지 마 푸른 꿈속으로