[백준] 30893 트리 게임(C++)

bfs를 통해 백준 문제를 풀어보자

[백준] 30893 트리 게임

문제

조건

이 문제는 트리가 주어질 때 선공과 후공중 이길 수 있는 공격 순서를 찾는 문제였다.

승리 조건
선공 → 플레이 중 목표 노드를 지날 수 있는 경우
후공 → 플레이 중 목표 노드를 지날 수 없는 경우

풀이 방식

일단 처음으로 생각한 것은 bfs와 dfs중에 어떤 방식으로 길을 찾아야 할지를 결정해야했다.
그럴려면 일단 선공과 후공에 따라 노드마다 선택권에 따라 최선의 선택을 한다는 가정을 구현하기 위해서 dfs를 통해 구현하는 것을 선택했다.
각 노드에 도착했을때 다음 노드를 모두 순회한 다음에 목표 노드로 갈 수 있는 길이 있는 경우 선택권이 선공에게 있는지 후공에게 있는지를 판단하고, 후공에게 있더라도 선택권이 1가지인 경우에는 선공이 이길 수 있다고 판단했다.
자세한 구현 코드는 아래에서 확인할 수 있다.

답안

참고자료

백준 트리 게임 풀러가기