백준 1761번 정점들의 거리

< 백준 1761번 정점들의 거리 - 마포 코딩박 >

사용한 알고리즘: LCA


 트리에서 두 점 사이의 최단거리를 구하는 문제였습니다.
두 점의 공통 조상까지의 거리를 구하고 그 거리를 구해 문제를 해결했습니다.

문제 풀이는 다음과 같습니다.

(1) 두 노드와 입력되는 거리 a, b, cost 를 pair< 노드, 거리 > 형식으로 저장합니다.
양방향 이므로 a에 <b, cost> , b에 <a, cost> 를 각각 자식으로 저장했습니다.

(2) 1번 노드를 Root 으로 설정하고, 트리를 구현합니다.
( LCA 구현이 어려운 분들은 강산님의 블로그
https://blog.naver.com/kks227/220820773477 를 참고해주세요)

(3) 공통 조상으로 가는 LCA 를 구현하면서, 그 과정에서 지나는 노드와의 거리 ( 과정 (1)에서 저장한 < 노드, 거리> 에서 거리값 )을 더해줍니다.

LCA 를 사용하는 문제라고 쉽게 알 수 있었습니다. LCA 구현을 잘 하는게 중요한 문제였습니다.