백준 21341번 Endgame

문제 요약

$ N \times N$ 보드가 주어진다. 그리고 사람 A, B의 말의 위치가 주어진다. A와 B는 말을 하나씩만 들고 있다. 그리고 각 말이 움직일 수 있는 방법이 $N$개 주어진다.

각 말이 한 턴에 할 수 있는 것은 $N$개의 움직이는 방법 중에 중복을 허용해서 두개를 골라서 수행하는 것이 있고, 원하는 곳으로 텔레포트를 하는 것이 있고 그냥 아무것도 안해도 된다.

다만, 움직이는 방법을 골라서 움직일 때만 상대방의 말을 잡을 수 있다.

현재 A와 B는 각각 순서대로 한 턴씩만 하고 게임을 끝내려고 한다. A가 먼저 턴을 시작할 것이다.

이 때, A가 이길 수 있다면 Alice Wins를 출력하고 이길 수 없지만 텔레포트를 해서 B가 A를 못잡게 할 수 있다면 tie x y를 출력하고, 둘 다 아니라면 Bob wins를 출력하시오. 이 때, x y는 A의 말이 무승부를 위해 움직여야 할 곳이다.

$ 1 \le N \le 10^5 $

풀이

$O(N^2)$풀이는 매우 간단하다. A, B가 갈 수 있는 곳을 전부 계산하고 A가 B를 잡을 수 있는지 확인하고 불가능하다면 B가 도달하지 못하는 곳이 있는지 확인하면 된다. $N$이 크기 때문에 이 방법은 불가능하다.

그렇다면 일단 두 말의 위치가 주어졌을 때 서로가 서로를 잡는 것이 가능한지 확인하는 것은 얼마나 걸릴까?

A의 위치에서 한 번의 움직임으로 갈 수 있는 곳은 최대 $N$개이고, 한 번의 움직임으로 $B$의 위치로 도달 할 수 있는 곳의 수도 최대 $N$개 이다. 두 집합 사이에 겹치는 것이 존재한다면 $A$는 $B$를 잡을 수 있는 것이다. 이 과정은 $O(NlogN)$으로 수행 가능하다.

이걸로 어떤 두 점 $P, Q$가 주어졌을 때, $P$가 $Q$를 잡아먹을 수 있는지 판단하는게 $O(NlogN)$에 되는 것을 확인했다. 그리고 A가 이길 조건을 체크하는 방법이기도 하다.

이제 무승부가 가능할지를 체크하는 방법을 생각하자. 가장 간단한 방법은 모든 점에 대해서 $B$가 잡아먹는 것이 가능한지를 테스트 해보는 것이다. $O(N^3logN)$으로 시간초과가 난다.

무승부가 불가능할 조건을 생각해보자. $B$에서 도달할 수 있는 곳이 보드 전체여야만 무승부가 불가능하다.

그런데 $N$이 적당히 클 때 $B$가 도달할 수 있는 곳이 그렇게 많을 수 있을까? 예제에서는 $N$이 2일 때는 가능하긴 한데 $N$이 100, 1000, 10000, 100000 이라면? 전부 도달할 수 있을까? 여기서 생각해볼 것이 $N$이 조금만 커져도 그럴 수 없다는 것을 알 수 있다.

대략적으로는 많아야 보드 전체의 $1/2$정도만 커버가능하다. 이는 $N$이 좀 큰 상황에서는 항상 무승부가 가능하다는 것이다. 게다가 임의로 점을 잡았을 때 무승부일 확률이 $1/2$보다는 크다는 것이다. 이를 이용해서 랜덤으로 점을 샘플링하는 것을 100번만 해도 그런 점을 찾을 확률이 매우 높다는 것을 알 수 있다.

따라서, $N$이 작을 때는 $O(N^2)$의 브루트 포스를 사용하고, $N$이 클 때는 임의로 점을 잡고 그 점이 무승부가 가능한 점일 때까지 이 과정을 반복하면 된다. 시간복잡도는 $O(NlogN)$으로 표현이 가능하긴 한데 상수가 큰 $O(NlogN)$ 정도가 되겠다.

#include<bits/stdc++.h>
using namespace std;
int N;
vector<pair<int,int>> moveset;
int ax, ay, bx, by;
bool vis[55][55];

inline bool valid(int y, int x) {
    return 1<=y && y<=N && 1<=x && x<=N;
}

void brute() {
    for(pair<int, int> p1 : moveset) {
        int x1 = ax + p1.first;
        int y1 = ay + p1.second;
        if(!valid(x1, y1)) continue;
        if(x1 == bx && y1 == by) {
            cout << "Alice wins" << '\n';
            return ;
        }
        for(pair<int, int> p2 : moveset) {
            int x2 = x1 + p2.first;
            int y2 = y1 + p2.second;
            if(!valid(x2, y2)) continue;
            if(x2 == bx && y2 == by) {
                cout << "Alice wins" << '\n';
                return ;
            }
        }
    }
    vis[bx][by] = true;
    for(pair<int,int> p1 : moveset) {
        int x1 = bx + p1.first;
        int y1 = by + p1.second;
        if(!valid(x1, y1)) continue;
        vis[x1][y1] = true;
        for(pair<int,int> p2 : moveset) {
            int x2 = x1 + p2.first;
            int y2 = y1 + p2.second;
            if(!valid(x2, y2)) continue;
            vis[x2][y2] = true;
        }
    }
    for(int i=1;i<=N;++i) {
        for(int j=1;j<=N;++j) {
            if(!vis[i][j]) {
                cout << "tie " << i << ' ' << j << '\n';
                return ;
            }
        }
    }
    cout << "Bob wins" << '\n';
    return ;
}

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cin >> N;
    cin >> ax >> ay;
    cin >> bx >> by;
    for(int i=0;i<N;++i) {
        int x, y; cin >> x >> y;
        moveset.emplace_back(x, y);
    }
    moveset.emplace_back(0, 0);
    if(N <= 50) {
        brute();
        return 0;
    }
    set<pair<int,int>> sa, sb;
    for(pair<int,int> p : moveset) {
        int x = bx + p.first;
        int y = by + p.second;
        if(valid(x, y)) sb.insert(make_pair(x, y));
        x = ax + p.first;
        y = ay + p.second;
        if(valid(x, y)) sa.insert(make_pair(x, y));
    }
    for(pair<int,int> p : moveset) {
        int x = bx - p.first;
        int y = by - p.second;
        if(!valid(x, y)) continue;
        if(sa.find(make_pair(x, y)) != sa.end()) {
            cout << "Alice wins" << '\n';
            return 0;
        }
    }
    srand(time(nullptr));
    while(1) {
        int x = (rand() % N) + 1;
        int y = (rand() % N) + 1;
        if(sb.find(make_pair(x, y)) != sb.end()) continue;
        set<pair<int,int>> s;
        for(pair<int,int> p : moveset) {
            if(!valid(x-p.first, y-p.second)) continue;
            s.insert(make_pair(x-p.first, y-p.second));
        }
        bool flag = true;
        for(pair<int,int> p : s) {
            if(sb.find(p) != sb.end()) {
                flag = false;
                break;
            }
        }
        if(flag) {
            cout << "tie " << x << ' ' << y << '\n';
            break;
        }
    }
    return 0;
}