문제 출처 : https://www.acmicpc.net/problem/1058

문제 정리

• 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람이 친구이거나, A와 친구이고, B와 친구인 C가 존재해야 된다.
• 여기서 가장 유명한 사람은 2-친구의 수가 가장 많은 사람이다. 가장 유명한 사람의 2-친구의 수를 출력하는 프로그램을 작성하시오.

문제 해결 방법

• 2-친구라는 의미를 풀어서 쓰면 그래프의 한 정점에서 거리가 1이나 2인 사람을 의미한다.

  즉, 한 정점에서 길이가 1이거나 2인 모든 정점의 개수를 찾으면 되는 문제라고 볼 수 있다.

• 플로이드 와샬 알고리즘을 사용한다.

코드

• click

코드 설명

• d배열에는 계산된 최소거리를 넣는다.

  플루이드 와샬 알고리즘을 계속 진행하면서 업데이트한다.

• 유명한 사람이 누군지 모르니 1번 사람부터 n번 사람까지 각각 2-친구를 구해줌

• if (i == j) continue;

  • 자기 자신과 친구가 될 수 없다. 그래서 제외를 해줌

주의사항