You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
reacted with thumbs up emoji reacted with thumbs down emoji reacted with laugh emoji reacted with hooray emoji reacted with confused emoji reacted with heart emoji reacted with rocket emoji reacted with eyes emoji
Uh oh!
There was an error while loading. Please reload this page.
Uh oh!
There was an error while loading. Please reload this page.
문제 링크
https://www.acmicpc.net/problem/15900
문제 조건
방법 1) BFS로 풀기
결국 모든 리프 노드가 부모 노드로 향하는데 지나치는 노드 수를 구한 뒤 그 수가 홀수이면 이기고 짝수이면 진다.
시간 복잡도
BFS에서 정점의 개수는 50만개, 간선의 개수는 (50만-1)개이므로 시간 안 풀이가 가능하다.
구현
방법 2) DFS 완전탐색으로 풀기
DFS를 돌면서 리프노드에 닿았을 때의 거리 값을 더해주는 방법도 있다. 그런데 시간이 더 오래걸린다.
All reactions