하나의 탐색 함수를 재귀적으로 구현해 내가 이기는 경우가 있다면 1, 어떤 경우도 내가 진다면 -1 리턴한다.

알고리즘 템플릿

int solve(int cur, int who) {
	// 종료 조건 작성. 문제의 조건에 따라 승리 시 1, 패배 시 -1 return
	if (cur == E) return who;
	if (edges[cur].size() == 1 && visited[edges[cur][0]]) return who * -1;

	visited[cur] = true;

	for (int v : edges[cur]) {
		if (visited[v])
			continue;

		// 하나라도 상대방이 지는 경우가 발견되면 나의 승리
		if (solve(v, who * -1) == -1)
			return 1;
	}
	// 모든 경우 패배
	return -1;
}

문제 및 풀이

트리 게임 (https://www.acmicpc.net/problem/30893)

• [Code]