C++로 세포 색칠 게임 승자 판별하기

문제 소개

각각 N개의 원소를 가진 두 배열 A와 B가 주어졌다고 가정해 봅시다. Amal과 Bimal은 셀 번호가 1부터 N까지 매겨진 보드 위에서 게임을 진행합니다. 보드에는 N-1개의 도로가 있으며, i번째 도로는 A[i]번 셀과 B[i]번 셀을 연결합니다. 어떤 셀이든 인접한 셀로 이동하는 과정을 반복하면 다른 모든 셀에 도달할 수 있습니다.

게임 시작 시 셀 1은 검은색으로, 셀 N은 흰색으로 칠해져 있고, 나머지 셀들은 아직 색칠되지 않은 상태입니다. Amal이 선공이며, 두 사람은 번갈아 가며 차례를 진행합니다. Amal은 검은색 셀에 인접한 색칠되지 않은 셀 하나를 골라 검은색으로 칠하고, Bimal은 흰색 셀에 인접한 색칠되지 않은 셀 하나를 골라 흰색으로 칠합니다. 더 이상 셀을 칠할 수 없게 된 플레이어가 패배하며, 우리는 최종 승자를 구해야 합니다.

예를 들어 입력이 A = [3, 1, 3, 7, 5, 1], B = [6, 2, 1, 4, 7, 4]라면 출력은 Amal입니다. Amal이 첫 수로 셀 2를 검은색으로 칠하면, Bimal이 어떤 수를 두더라도 Amal이 승리하기 때문입니다.

해결 접근 방식

도로들이 트리 구조를 이루므로, 이 게임은 본질적으로 검은 뿌리(셀 1)와 흰 뿌리(셀 N) 사이의 경로를 중심으로 벌어지는 영역 다툼입니다. 핵심 아이디어는 다음과 같습니다.

DFS(깊이 우선 탐색)를 통해 각 노드의 부모, 깊이, 서브트리 크기를 계산합니다.
셀 N에서 부모 포인터를 따라 (d[n] - 1) / 2번 올라가면, 셀 1과 셀 N을 잇는 경로의 중간 지점 노드를 찾을 수 있습니다.
중간 노드의 서브트리 크기의 2배가 전체 노드 수 n보다 크거나 같으면 Bimal이, 그렇지 않으면 Amal이 승리합니다.

이를 의사코드로 표현하면 다음과 같습니다.

N := 99999
인접 리스트 adjList 정의
큰 배열 p, d, ssz 세 개 정의
dfs(nd, par, dep) 함수 정의:
    p[nd] := par
    d[nd] := dep
    ssz[nd] := 1
    adjList[nd]의 각 노드 i에 대해:
        i XOR par이 0이 아니면:
            dfs(i, nd, dep + 1)
            ssz[nd] := ssz[nd] + ssz[i]
메인 메서드에서는 다음을 수행:
n := A의 크기
i := 1부터 i < n일 때까지(i는 1씩 증가):
    u := A[i - 1], v := B[i - 1]
    adjList[u] 끝에 v 삽입
    adjList[v] 끝에 u 삽입
dfs(1, 1, 0) 호출
nd := n
i := 0부터 i < (d[n] - 1) / 2일 때까지(i는 1씩 증가):
    nd := p[nd]
2 * ssz[nd] >= n이면 "Bimal" 반환, 아니면 "Amal" 반환

C++ 구현 예제

더 나은 이해를 돕기 위해 다음 구현 예제를 살펴보겠습니다.

#include <bits/stdc++.h>
using namespace std;

int N = 99999;

vector<vector<int>> adjList(N);
vector<int> p(N), d(N), ssz(N);

void dfs(int nd, int par, int dep){
    p[nd] = par;
    d[nd] = dep;
    ssz[nd] = 1;
    for (int i : adjList[nd]){
        if (i ^ par){
            dfs(i, nd, dep + 1);
            ssz[nd] += ssz[i];
        }
    }
}
string solve(vector<int> A, vector<int> B){
    int n = A.size();
    for (int i = 1; i < n; i++){
        int u = A[i - 1], v = B[i - 1];
        adjList[u].push_back(v);
        adjList[v].push_back(u);
    }
    dfs(1, 1, 0);
    int nd = n;
    for (int i = 0; i < (d[n] - 1) / 2; i++)
        nd = p[nd];
    return (2 * ssz[nd] >= n ? "Bimal" : "Amal");
}
int main(){
    vector<int> A = { 3, 1, 3, 7, 5, 1 };
    vector<int> B = { 6, 2, 1, 4, 7, 4 };
    cout << solve(A, B) << endl;
}

입력

{ 3, 1, 3, 7, 5, 1 }, { 6, 2, 1, 4, 7, 4 }

출력

Amal