BOJ 32528 월간 훈수회

📝 문제 정보

#

• 링크: 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});
    }
}