solve.ac class1 [백준 1389] 케빈 베이컨의 6단계 법칙 [Python] 풀이 'Six Degrees of Separations' theory로도 불리는 이론이다. 자신과는 아무 연관성(inf or V) 없는 사람일지라도, 만약 친구가 한 명 이상 있다면(connected), 대부분 6단계(5명의 관계)를 걸쳐 알 수 있게 된다는 이론이다. 즉, 당신이 6단계를 넘어선다면 아싸일 확률이 매우 높... 문제에서 "모든 사람은 친구 관계로 연결되어져 있다." 라고 하여 주어지는 TC에 대한 별도의 예외처리는 없다. Floyd Warshall을 이용해 모든 친구 관계에 대해서 최단 단계를 구해주고, 각각의 유저가 모든 유저간에 대한 단계의 합으로이루어진 집합(step) 속 최솟값의 순번을 구하자. 소스코드 소스코드 보기 출처 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의.. 2023. 4. 8. 이전 1 다음
