일지 & 개발

문제 요약 알고리즘 분류: 플로이드 워셜 난이도: Gold4 문제내용: 각 노드간의 최단 거리를 구해라 시작과 도착점은 같은 거리는 없다. 시작점에서 도착점까지 갈수 없으면 0으로 표시한다. 사이트: https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 문제풀이 이번에는 문제 유형은 그래프 탐색 관련 문제이다. 모든 노드간의 최단 거리를 구하라는 문제가 나와있고 데이터가 최대 100으로 봤을때 플로이드 워셜 알고리즘으로 해결 할 수가 있다. 시간복잡..

이론 이번에 볼 알고리즘은 플로이드-워셜이다. 플로이드 워셜은 다익스트라 알고리즘이랑 비슷한점은 a → b 최단 거리를 구하는 것인데 다익스트라는 시작점과 끝점이 있다는것고 플로이드 워셜은 각 노드간의 최단 거리를 구하는 것이다. 하지만 다익스트라와 다르게 구현이 간단하는데 시간복잡도는 O(N^3)이라는 긴 시간 복잡도를 간진다. 자세한 설명은 아래의 사이트에서 확인 해봐라 https://namu.wiki/w/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%9B%8C%EC%85%9C%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 플로이드-워셜 알고리즘 - 나무위키 이 저작물은 CC BY-NC-SA 2.0 KR에 따라 이용할 수 있습니다. (단, 라이선스가 ..