플로이드-워셜 알고리즘 그래프에서, 한 정점에서 다른 정점으로 가는 최단거리가 있다. 플로이드-워셜 알고리즘을 사용한다면 각각의 모든 정점에서 모든 정점으로 가는 최단거리를 전부 구할 수 있다. 즉, 1 ~ 2, 1 ~ 3, 1 ~ N 2 ~ N 3 ~ N 4 ~ N 5 ~ N 모든 경로에서 전부 최단 거리를 구할 수 있다. 2 -> 1로 가는 최단 경로를 볼 때, 2 -> 1은 9 2 -> 3 -> 1은 7로 노드 3을 거쳐가는 것이 더 빠름 이렇게 노드를 거쳐서 가는게 더 빠른 경로까지도 플루이드-워셜 알고리즘을 통해 구할 수 있다는 것이다. 플로이드-워셜 알고리즘은 DP(Dynamic Programming) 기법을 사용한 알고리즘이다. 즉, 노드 0개를 거쳐가는 최단거리를 구하고, 노드 1개, 노드..

그래프(Graph)란? 그래프는 vertex와 edge로 구성된 한정된 자료구조를 의미한다. vertex : 정점 edge : 정점과 정점을 연결하는 간선 아래는 대표적인 그래프 종류들의 예시다. 이러한 그래프는 인접 행렬, 인접 리스트 방식으로 표현할 수 있다. 그래프 구현 - 인접 행렬 먼저, 행렬로 구현하는 방식을 살펴보자 정점 a와 정점 b를 잇는 간선이 있을 경우, 행렬(a,b)에 1을 표기해준다. 만약 가중치가 있는 그래프라면 1 대신 가중치를 넣을 수 있다. 기본적으로 무방향 그래프의 경우는 (a,b) (b,a)에 모두 간선 값을 넣지만, 방향 그래프같은 경우는 위의 표와 같이 방향에 맞는 간선만 표기한다. ex) 정점 1과 3을 잇는 간선이 존재할 때 : graph[1][3] = 1, gr..