플로이드 워셜 알고리즘1 [백준] 1389번 - 케빈 베이컨의 6단계 법칙 [Java] https://www.acmicpc.net/problem/1389 1. 아이디어 케빈 베이컨 수는 그래프에서 특정 노드와 다른 모든 노드와의 거리의 합과 같다. 각 사람에 대해 BFS 알고리즘으로 거리를 구해서 더하는 방식과 플로이드 워셜 알고리즘으로 거리 배열을 구해서 더하는 방법 두가지로 해결할 수 있었다.2. 문제풀이 - BFS친구관계가 중복으로 들어올 수 있어서 인접 리스트에 Set을 적용해서 중복을 제거하는 방식으로 구현했다. - 플로이드 워셜 알고리즘각 친구들과의 거리 정보를 담은 거리 배열을 생성한 후 각 행 또는 열의 합으로 케빈 베이컨 수를 간단하게 구할 수 있다.3. 코드 import java.io.*;import java.util.*;public class Main_BFS { .. 2025. 1. 23. 이전 1 다음
