임의의 그래프 위에서의 게임¶
두 명의 플레이어가 임의의 그래프 $G$ 위에서 게임을 한다고 합시다. 즉, 게임의 현재 상태는 어떤 정점입니다. 플레이어들은 번갈아 가며 수를 두며, 연결하는 간선을 이용하여 현재 정점에서 인접한 정점으로 이동합니다. 게임에 따라 이동할 수 없는 사람이 게임에서 지기도 하고 이기기도 합니다.
가장 일반적인 경우, 즉 사이클이 있는 임의의 방향 그래프의 경우를 고려합니다. 우리의 과제는 초기 상태가 주어졌을 때 두 플레이어가 모두 최적의 전략으로 플레이한다면 누가 게임에서 이기는지 판단하거나, 게임의 결과가 무승부가 된다는 것을 판단하는 것입니다.
이 문제를 매우 효율적으로 풀어 보겠습니다. 그래프의 가능한 모든 시작 정점에 대한 답을 간선의 개수에 대해 선형 시간인 $O(m)$에 구하겠습니다.
알고리즘 설명¶
어떤 정점에서 시작하는 플레이어가 최적으로 플레이할 때 (상대 플레이어가 어떤 수를 두든 상관없이) 게임에서 이긴다면, 그 정점을 승리 정점이라고 부르겠습니다. 마찬가지로, 어떤 정점에서 시작하는 플레이어가 상대가 최적으로 플레이할 때 게임에서 진다면, 그 정점을 패배 정점이라고 부르겠습니다.
그래프의 일부 정점에 대해서는 승리 정점인지 패배 정점인지 이미 미리 알고 있습니다. 바로 나가는 간선이 없는 모든 정점입니다.
또한 다음과 같은 규칙이 있습니다.
- 어떤 정점에 패배 정점으로 이어지는 나가는 간선이 있다면, 그 정점 자체는 승리 정점입니다.
- 어떤 정점의 나가는 간선이 모두 승리 정점으로 이어진다면, 그 정점 자체는 패배 정점입니다.
- 어느 시점에 아직 결정되지 않은 정점이 남아 있고 그중 어느 것도 첫 번째나 두 번째 규칙에 맞지 않는다면, 이 정점들 각각은 시작 정점으로 사용되었을 때 두 플레이어가 모두 최적으로 플레이하면 무승부가 됩니다.
따라서 $O(n m)$ 시간에 동작하는 알고리즘을 바로 정의할 수 있습니다. 모든 정점을 살펴보며 첫 번째 또는 두 번째 규칙을 적용해 보고, 이를 반복합니다.
하지만 이 과정을 가속하여 복잡도를 $O(m)$까지 낮출 수 있습니다.
처음부터 승리 상태인지 패배 상태인지 알고 있는 모든 정점을 살펴봅니다. 각 정점에 대해 깊이 우선 탐색을 시작합니다. 이 DFS는 역방향 간선을 따라 거슬러 이동합니다. 우선, 이미 승리 정점이나 패배 정점으로 정해진 정점에는 들어가지 않습니다. 그리고 탐색이 패배 정점에서 결정되지 않은 정점으로 이동하면, 그 정점을 승리 정점으로 표시하고 이 새 정점에서 DFS를 계속합니다. 승리 정점에서 결정되지 않은 정점으로 이동하면, 그 정점에서 나가는 모든 간선이 승리 정점으로 이어지는지 확인해야 합니다. 각 정점마다 승리 정점으로 이어지는 간선의 개수를 저장해 두면 이 검사를 $O(1)$에 수행할 수 있습니다. 따라서 승리 정점에서 결정되지 않은 정점으로 이동하면 카운터를 증가시키고, 이 수가 나가는 간선의 개수와 같은지 확인합니다. 같다면 이 정점을 패배 정점으로 표시하고 이 정점에서 DFS를 계속할 수 있습니다. 그렇지 않다면 이 정점이 승리 정점인지 패배 정점인지 아직 알 수 없으므로, 이 정점에서 DFS를 계속 진행하는 것은 의미가 없습니다.
전체적으로 모든 승리 정점과 모든 패배 정점을 정확히 한 번씩 방문하며(결정되지 않은 정점은 방문하지 않습니다), 각 간선도 최대 한 번만 지나갑니다. 따라서 복잡도는 $O(m)$입니다.
구현¶
다음은 이러한 DFS의 구현입니다. 변수 adj_rev에는 그래프의 인접 리스트가 뒤집힌 형태로 저장되어 있다고 가정합니다. 즉, 그래프의 간선 $(i, j)$ 대신 $(j, i)$를 저장합니다. 또한 각 정점의 나가는 차수는 이미 계산되어 있다고 가정합니다.
vector<vector<int>> adj_rev;
vector<bool> winning;
vector<bool> losing;
vector<bool> visited;
vector<int> degree;
void dfs(int v) {
visited[v] = true;
for (int u : adj_rev[v]) {
if (!visited[u]) {
if (losing[v])
winning[u] = true;
else if (--degree[u] == 0)
losing[u] = true;
else
continue;
dfs(u);
}
}
}
예제: "경찰과 도둑"¶
다음은 이러한 게임의 구체적인 예입니다.
$m \times n$ 크기의 판이 있습니다. 일부 칸에는 들어갈 수 없습니다. 경찰과 도둑의 초기 좌표는 알려져 있습니다. 칸 중 하나는 출구입니다. 어느 순간이든 경찰과 도둑이 같은 칸에 있으면 경찰이 이깁니다. 도둑이 출구 칸에 있으면(경찰이 같은 칸에 있지 않은 경우) 도둑이 이깁니다. 경찰은 8방향 모두로 이동할 수 있지만, 도둑은 4방향(좌표축 방향)으로만 이동할 수 있습니다. 경찰과 도둑은 번갈아 가며 이동합니다. 하지만 원한다면 차례를 건너뛸 수도 있습니다. 첫 번째 이동은 경찰이 합니다.
이제 그래프를 구성하겠습니다. 이를 위해 게임의 규칙을 형식화해야 합니다. 게임의 현재 상태는 경찰의 좌표 $P$, 도둑의 좌표 $T$, 그리고 누구의 차례인지에 의해 결정됩니다. 이 마지막 변수를 $P_{\text{turn}}$이라고 부르겠습니다(경찰의 차례일 때 참입니다). 따라서 그래프의 정점은 세 값의 조합 $(P, T, P_{\text{turn}})$으로 결정됩니다. 그러면 게임의 규칙을 그대로 따르기만 해도 그래프를 쉽게 구성할 수 있습니다.
다음으로, 초기에 어떤 정점이 이기는 정점이고 어떤 정점이 지는 정점인지 결정해야 합니다. 여기에는 미묘한 점이 있습니다. 이기는 정점과 지는 정점은 좌표뿐만 아니라 $P_{\text{turn}}$, 즉 누구의 차례인지에도 의존합니다. 경찰의 차례라면, 경찰과 도둑의 좌표가 일치할 때 그 정점은 승리 정점이고, 승리 정점이 아니면서 도둑이 출구 정점에 있을 때 그 정점은 패배 정점입니다. 도둑의 차례라면, 두 플레이어의 좌표가 일치할 때 그 정점은 패배 정점이고, 패배 정점이 아니면서 도둑이 출구 정점에 있을 때 그 정점은 승리 정점입니다.
구현하기 전에 짚어 둘 점은 단 하나로, 그래프를 명시적으로 구축할지 아니면 즉석에서 구성할지 결정해야 한다는 것입니다. 한편으로는, 그래프를 명시적으로 구축하는 편이 훨씬 쉽고 실수할 가능성도 적습니다. 다른 한편으로는, 코드의 양이 늘어나고 그래프를 즉석에서 구성할 때보다 실행 시간이 느려집니다.
다음 구현은 그래프를 명시적으로 구축합니다:
struct State {
int P, T;
bool Pstep;
};
vector<State> adj_rev[100][100][2]; // [P][T][Pstep]
bool winning[100][100][2];
bool losing[100][100][2];
bool visited[100][100][2];
int degree[100][100][2];
void dfs(State v) {
visited[v.P][v.T][v.Pstep] = true;
for (State u : adj_rev[v.P][v.T][v.Pstep]) {
if (!visited[u.P][u.T][u.Pstep]) {
if (losing[v.P][v.T][v.Pstep])
winning[u.P][u.T][u.Pstep] = true;
else if (--degree[u.P][u.T][u.Pstep] == 0)
losing[u.P][u.T][u.Pstep] = true;
else
continue;
dfs(u);
}
}
}
int main() {
int n, m;
cin >> n >> m;
vector<string> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
for (int P = 0; P < n*m; P++) {
for (int T = 0; T < n*m; T++) {
for (int Pstep = 0; Pstep <= 1; Pstep++) {
int Px = P/m, Py = P%m, Tx = T/m, Ty = T%m;
if (a[Px][Py]=='*' || a[Tx][Ty]=='*')
continue;
bool& win = winning[P][T][Pstep];
bool& lose = losing[P][T][Pstep];
if (Pstep) {
win = Px==Tx && Py==Ty;
lose = !win && a[Tx][Ty] == 'E';
} else {
lose = Px==Tx && Py==Ty;
win = !lose && a[Tx][Ty] == 'E';
}
if (win || lose)
continue;
State st = {P,T,!Pstep};
adj_rev[P][T][Pstep].push_back(st);
st.Pstep = Pstep;
degree[P][T][Pstep]++;
const int dx[] = {-1, 0, 1, 0, -1, -1, 1, 1};
const int dy[] = {0, 1, 0, -1, -1, 1, -1, 1};
for (int d = 0; d < (Pstep ? 8 : 4); d++) {
int PPx = Px, PPy = Py, TTx = Tx, TTy = Ty;
if (Pstep) {
PPx += dx[d];
PPy += dy[d];
} else {
TTx += dx[d];
TTy += dy[d];
}
if (PPx >= 0 && PPx < n && PPy >= 0 && PPy < m && a[PPx][PPy] != '*' &&
TTx >= 0 && TTx < n && TTy >= 0 && TTy < m && a[TTx][TTy] != '*')
{
adj_rev[PPx*m+PPy][TTx*m+TTy][!Pstep].push_back(st);
++degree[P][T][Pstep];
}
}
}
}
}
for (int P = 0; P < n*m; P++) {
for (int T = 0; T < n*m; T++) {
for (int Pstep = 0; Pstep <= 1; Pstep++) {
if ((winning[P][T][Pstep] || losing[P][T][Pstep]) && !visited[P][T][Pstep])
dfs({P, T, (bool)Pstep});
}
}
}
int P_st, T_st;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (a[i][j] == 'P')
P_st = i*m+j;
else if (a[i][j] == 'T')
T_st = i*m+j;
}
}
if (winning[P_st][T_st][true]) {
cout << "Police catches the thief" << endl;
} else if (losing[P_st][T_st][true]) {
cout << "The thief escapes" << endl;
} else {
cout << "Draw" << endl;
}
}