[백준/C++][(1761번)정점들의 거리]

문제

https://www.acmicpc.net/problem/1761

1761번: 정점들의 거리

문제해결

1.벡터에 정점과 가중치를 입력받는다.

2.DFS를 통해서 각 노드들마다 부모와 깊이를 알아낸다.

3.LCA알고리즘을 실행한다

3-1. 만약 두 노드가 같으면 출력한다

3-2. 두 노드가 같지 않고 깊이가 같으면 두 노드 다 깊이-1로 이동한다.

3-3  한 노드가 다른노드보다 깊이가 크면 큰 노드가 깊이-1로 이동한다.

4. 두 노드가 같아 질때까지 반복한다.

 

코드

ide.goorm.io/shared_files/sksj0111_fdcaefbb66aa200201435bf2dd65aa471605796486050

1761.cpp - goorm