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

문제 정리

• 상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이다. 상근이의 학번은 1이다.
• 상근이는 동기들의 친구 관계를 모두 조사한 리스트를 가지고 있다. 이 리스트를 바탕으로 결혼식에 초대할 사람의 수를 구하는 프로그램을 작성하시오.

문제 해결 방법

모든 정점에서 모든 장점으로 최단 경로를 구하고 2이하의 값을 찾으면 되는 문제라서 플로이드 와샬 알고리즘을 사용했다.

→ 플로이드 와샬 알고리즘

코드

• click

코드 설명

1. 플로이드 와샬 알고리즘을 적용해서 풀었다.

2. 자기 자신은 초대를 할 수 없으니 제외한다.

3. 상근이는 1번이므로 d[1][]에서 2 이하의 값을 다 찾아준다.

주의사항