플로이드 워셜

문제 링크 : https://www.acmicpc.net/problem/1389 이 문제는 전형적인 플로이드 워셜 알고리즘을 이용하여 해결할 수 있는 문제이다. 예제 입력을 그래프로 표현하면 위와 같다. 여기서 단방향이 아니라는 것에 주의해서거리 배열을 초기화한다. 거리배열을 초기화하면 인접 정점끼리의 관계를 표현할 수 있다.여기서 무한대는 문제의 조건을 보고 직접 적당히 큰 값을 넣거나,아니면 Interger.MAX_VALUE와 같이 int 범위에서 가장 큰 값을 넣어주면 된다.다만 이럴 경우에는 연산의 과정에서 int의 범위를 넘어 오버플로우가 발생할 수 있기 때문에long 타입으로 캐스팅한 후에 연산을 해줘야 한다. 거리배열을 초기화한 후에는 플로이드 워셜 알고리즘으로 각 정점사이의 최단거리를 구해..

문제 링크 : https://www.acmicpc.net/problem/11403 특정 정점에서 각 정점까지 연결이 되어있는지를 물어보는 문제이다.플로이드 워셜 알고리즘을 이용하면 되는데 여기서 이 문제는 최단거리를 물어보는 문제가 아니기 때문에 이 문제와는 다르게 최단거리를 업데이트해주는 부분만 변형해 주면 된다. 플로이드 워셜이 S부터 E까지의 최단 거리는 S와 E 사이에 있는 K 정점을 기준으로 S -> K + K -> E까지의 거리가 기존의 S -> E 까지의 거리보다 가깝다면 업데이트를 해주는 방식이었다. 이 문제에서는 S -> K 까지 연결되어 있고 K -> E까지 연결되어 있다면 S -> E는 연결되어 있다는 로직으로수정해 주면 된다. package boj;import java.util.*;..

문제 링크 : https://www.acmicpc.net/problem/11404 문제의 이름이 플로이드인 만큼 플로이드-워셜 알고리즘을 사용하는 문제이다.플로이드 워셜 알고리즘은 모든 정점사이 간의 최단거리를 알아내는 알고리즘으로정점의 개수가 N 이라고 했을 때 시간복잡도가 O(N^3)인 알고리즘이다.따라서 플로이드 워셜 알고리즘을 사용하는 문제는 정점의 개수인 N이 작다는 특징이 있다. 우선 플로이드 워셜 알고리즘을 구현하기 위해 인접 행렬을 만들어주고값을 채워준다. 여기서 값이 의미하는 것은 arr[S][E] 는 정점 S부터 정점 E 까지 가는데 드는 최소비용이라는 의미이다.여기서 S와 E가 동일하다면 움직이지 않는것을 의미하기 때문에 0으로 초기화해준다. 그리고 3중 for문을 이용해서 위의 점화..