https://www.acmicpc.net/problem/30893
문제요약
- 트리가 주어짐. 시작노드 S, 끝 노드 E
- 번갈아가며 노드를 이동. 인접한 곳으로만 이동. 한 번 방문한 곳은 가면 안됨
- 게임이 끝났을때 E를 방문했으면 선공이 승리. 아니면 패배
- 이기려면 선공을 골라야할까? 후공을 골라야할까?
접근법
- 문제를 잘 이해해야함
- 더 이상 움직이지 못하면 게임은 끝남. 또는 E에 도착해도 게임은 끝남
- 그리고 E에 도착하면 선공이 이김
- 선공 : 어떻게든 E로만 가면 됨
- 후공 : 어떻게든 E가 없는 쪽으로 가서 더 이상 움직이지 못하면 됨
- 트리의 특성상 자식 노드로만 이동할 것임
- 이런 특성을 이용해서 선공/후공 입장에서 그래프를 탐색
newbieski