목록1389 (1)

설모의 기록

[백준 1389] 케빈 베이컨의 6단계 법칙

이 문제는 그래프에서 한 정점에서 다른 정점으로 가는 최단경로의 합이 가장 작은 정점을 구하는 문제입니다. dfs나 bfs로 해도 풀리겠지만, 처음 알게 된 폴로이드 와샬 알고리즘을 적용해보기 위해 저는 이 알고리즘을 사용했습니다. 폴로이드 와샬 알고리즘 정점 사이의 최단경로를 구할 때에 자주 사용하는 것이 다익스트라 알고리즘인데요. 다익스트라 알고리즘의 단점은 정점 사이의 가중치가 음수일 때 사용할 수 없다는 점입니다. 이에 반해 폴로이드 와샬 알고리즘은 가중치가 음수여도 사용이 가능합니다. 이름이 어렵게 생겨서 뭐지? 했는데 알고 보니 3중 포문을 이용해 모든 정점과 정점사이의 거리를 구하는 알고리즘이었습니다. 먼저 kebin이라는 int[][] 배열을 초기화하고, 주어진 정점들의 관게를 입력합니다...
알고리즘 2018. 5. 2. 19:38
이전 Prev 1 Next 다음