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.
문제 링크
https://www.acmicpc.net/problem/1240
문제 조건
아이디어
트리의 특성상 모든 노드는 연결되어 있다는 것을 이용해 주어진 두 정점 중 아무거나 하나를 잡고 시작해 다른 하나에 도달할 때까지의 거리를 계산했다.
이렇게 하니까 성공은 하는데 시간이 너무 오래 걸렸다.
곰곰히 생각해보니 거리를 계산하는 것이므로 BFS가 더 알맞는 풀이인 것 같다.
트리라고 무조건 DFS 써야겠다는 생각을 버려야겠다!
BFS로 바꾸고 나서 시간이 매우 많이 줄어들었지만 그래도 오래 걸렸다.
시간 복잡도를 생각해보니 M번 동안 BFS를 도는데 BFS는 (N^2)의 시간이 걸렸다.
최댓값을 생각해보면 O(10^9)으로 2초 안에 풀이가 불가능하다. (근데 제출하면 통과하긴 한다^)
좀 더 효율적인 방법이 없을까하고 다른 사람들의 풀이를 보니 기가맥힌 알고리즘을 발견했다.
LCA라는 알고리즘인데 최소 공통 조상을 찾는 알고리즘이다.
두 노드 사이의 거리 = 노드 1에서 루트까지의 거리 + 노드 2에서 루트까지의 거리 - 2*LCA까지의 거리뭐 이런식으로 구한다고 하는데 시간이 없으니 다음에 알아보자^
구현
All reactions