문제 링크 : 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문을 이용해서 위의 점화..

문제 링크 : https://www.acmicpc.net/problem/1854 이 문제는 시작 정점부터 각각의 정점까지의 최단 거리를 찾는 다익스트라 알고리즘을 변형한 문제이다.단순히 최단 거리가 아닌 k번째 최단 경로를 구해야 한다.일반적으로 다익스트라 알고리즘은 각 정점까지 최단거리만을 저장하는 배열을 가지고 있는데이 문제를 해결하기 위해서는 각 정점까지의 거리 중 k번째로 짧은 거리까지 저장할 수 있는 자료구조가 필요하다. 여기서 PriorityQueue를 사용하면 매번 따로 처리해주지 않아도편하게 k번째 최단거리를 구할 수 있다. 일반적인 다익스트라 알고리즘 문제에서는 인접 리스트를 구현해서 푸는 것이 더 편하지만이 문제를 해결하기 위해서는 이런 인접 행렬을 이용해야 한다.arr[1][2] = ..