[엘리스 알고리즘 코드 챌린지 시즌 2] 예선 4일 [Python]

풀이

루트가 1번인 트리에서 하나의 말을 "두 사람이 최적으로" 번갈아가며 점수를 얻고 말을 이동하는 문제다.

문제에서 주어진 두 사람이 최적으로 라는 지문의 의미는 결국 시작 정점을 기준으로 자신의 점수를 가장 높이는 방향으로 게임을 끝내는 것을 의미한다.

 

우선 간선을 입력받아 양방향 그래프를 생성하자.

이제 dfs로 리프노드까지 탐색하며 역순으로 부모노드에 대한 점수를 계산하고자 한다.

양방향 그래프이므로 자식 노드로만 탐색을 해주자.

리프노드 까지 탐색을 완료했다면 가장 적은 점수차를 dp에 갱신해주자.

만약 자식이 없다면(리프노드) 자신의 번호가 자신의 점수가 되므로 diff를 0으로 계산해주자.

 

예선 3일차에서도 유명한 문제임에 비해 예외가 적용되지 않는 오류가 있었고, 제공되는 자료와 맞지않는 문제가 주어진다는 점을 미루어 볼 때 아쉬운 점이 많이 남는 챌린지다.

---

소스코드

보기

---

출처

엘리스 코드 챌린지