태그:
N명의 사람과 그 관계가 주어질 때, 다른 사람들과의 관계의 거리의 합이 가장 작은 사람을 찾는 문제입니다. 다른 말로 바꿔서 말하면 그래프의 한 점에서 다른 모든 점까지의 최단 거리의 합을 구하는 문제입니다. 최단 거리를 구하는 문제이므로 BFS로 풀 수 있고, 모든 점과 점의 쌍에 대해 최단 거리를 구하는 문제이기도 하니 플로이드-와셜을 쓸 수도 있겠지만 그건 제가 아직 모릅니다.그러면 왜 써놓는건데 아무튼 BFS를 이용하여 점과 점 사이의 최단 거리를 구하고, 그 합의 최소값이 같은 경우 인덱스가 작은 사람을 출력하는 조건에 따라 알맞은 인덱스를 출력하면 됩니다.
소스 코드
| 언어 | 코드 | 시간 |
|---|---|---|
| C++ | 코드(Github) / 코드(백준) | 2020-12-25 19:16:02 |