Functional_graph

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/32528 🧐 관찰 및 접근 # 오늘도 찾아온 게임이론 문제이다. 주어진 그래프는 함수형 그래프이다. 함수형 그래프는 사이클 하나와, 해당 사이클로 들어가는 간선들의 모양을 가진다. 정점은 $N$개, 간선은 $N$개이다. 일단 선공 $A$가 $B$의 앞 칸을 끊어버렸다고 가정하자. 함수형 그래프이므로 앞 칸은 언제나 존재한다. 후공 $B$는 자신의 이웃한 정점으로 이동할 수가 없다. 따라서, 어떤 정점 하나를 삭제하는 수밖에 없다. 선공 $A$의 턴의 경우의 수를 줄이기 위해, 해당 정점도 $A$의 앞 칸이었다고 가정하자. 그렇다면 현재 남은 정점은 $N-2$개이므로, $N$이 짝수일때는 후공이, 홀수일때는 선공이 이기게 된다. 그렇다면 $N$이 짝수일때는 선공이 $B$의 앞칸을 끊는것이 손해인가? 시작 위치에서 $B$가 $A$의 앞에 있었다고 생각해보자. 그렇다면 $A$는 두번째 자신의 턴에서 $B$의 위치로 이동할 수 있고, 이후 삭제할 수 있는 정점의 개수는 $N-1$개, 턴은 $B$의 턴이다. 따라서 이때는 선공이 승리한다. 따라서, $N$이 홀수이거나, $N$이 짝수이면서 $B$가 $A$의 앞 칸이라면 선공이 무조건 승리할 수 있다. $N$이 짝수고 $B$가 $A$의 앞칸이 아니라면 라면 선공이 어떻게 하면 좋을까? 상대한테 턴을 넘기는 편이 유리할 것 같다. 그러면 $A$가 한칸 앞으로 간다고 해보자. 이때 $B$는 또한 $A$를 억제하기 위해 위와 같은 행동을 할 수 있고, 이때 $N$은 짝수로 고정되어있으므로 $A$가 $B$의 앞칸이라면 후공이 무조건 승리할 수 있고, 그렇지 않다면 $B$도 한칸 앞으로 갈 것이다. 이는 사이클 안에 갇힐때까지 반복된다! 풀이를 요약해보자. 둘이 같은 칸에 있을때는, 그때부터 N-1개 정점 지우기 게임이 된다. $N$이 홀수일때는 나중에 행동하는 쪽이, 짝수일때는 먼저 행동하는 쪽이 이기게 된다. 상대의 앞 칸을 지울 수 있고, $N$이 홀수라면 바로 들어가서 삭제를 거는게 이득이다. 아니라면 이동을 할텐데, 그 이동을 한 결과 상대의 승리조건을 만족시켜버린다면 그냥 아무 정점이나 지워버려서 그런 상황이 오지 못하게 만들자. 💻 풀이 # 코드 (C++): void solve(){ int N; cin >> N; int A, B; cin >> A >> B; vector<int> nxt(N+1); rep(i, 1, N+1) cin >> nxt[i]; set<tuple<int, int, bool>> st; st.insert({A, B, true}); bool Aturn = true; while(true){ // cout << A << ' ' << B << ' ' << Aturn << '\n'; if(A == B){ if(N%2) cout << (Aturn ? "second" : "first"); else cout << (Aturn ? "first" : "second"); return; } if(Aturn && (nxt[B] != A && N%2)){ cout << "first"; return; } if(!Aturn && (nxt[A] != B && N%2)){ cout << "second"; return; } if(Aturn && nxt[nxt[A]] != B && N%2) N--; else if(!Aturn && nxt[nxt[B]] != A && N%2) N--; else if(Aturn) A = nxt[A]; else B = nxt[B]; Aturn = !Aturn; if(st.count({A, B, Aturn})){ cout << "draw"; return; } st.insert({A, B, Aturn}); } } 🔒 구현 코드 잠금