백준1 2. 플로이드 와샬 플로이드 와샬을 사용하는 경우는? 플로이드 와샬은 그래프 알고리즘 중 하나라고 할 수 있다. 각각의 정점에서 다른 각각의 정점으로 가는 최단거리를 구하는 알고리즘이다. 이게 무슨 소리일까? 처음에는 다른 블로그들을 봤을 때 잘 이해가 안갔었는데, 이해하고 나서 막상 쓰려다보니 저 말이 맞는 말이다. 이해가 잘 안갔던 기억을 토대로 이 글에서 좀 자세하게 알고리즘에 대해 설명 해보고자 한다. 플로이드 와샬 알고리즘 아래 그림을 살펴본다. 단순히 그래프를 직관적으로 봤을 때, 출발지에서 도착지까지 어딘가 경유하지 않고 한 번에 갈 수 있는 거리를 오른쪽 표로 나타낸 것이다. 이제부터 오른쪽 표를 하나씩 채워가며 완성할 건데, 이때 모든 칸들을 최솟값으로 채우는 알고리즘이 바로 플로이드 와샬 알고리즘이다. 즉.. 2023. 3. 2. 이전 1 다음
