목록21278 (1)

계단을 오르듯이

[JAVA] 21278. 호석이 두 마리 치킨

플로이드-와샬 알고리즘을 이용해야한다. 플로이드 와샬 알고리즘은 O(n^3)의 시간복잡도를 가지며, 모든 정점의 이동거리를 구할 수 있다. 총 n개의 정점이 있다면 1개의 노드가 n-1의 노드까지의 연결 거리를 모두 알 수 있다. 우선 플로이드-와샬 알고리즘을 통해 서로의 연결 상태(간선의 개수)를 알 수 있고, 간선의 개수만큼의 시간이 걸린다. 현재 문제에서는 왕복의 거리이므로 간선의 수 한개당 2의 시간이 걸린다고 생각하고 시간 배열을 채웠다. 그 후, 치킨집을 조합으로 하여 모든 경우의 수를 통해 최소의 거리시간을 구하였다. 우선 2개의 치킨집을 조합으로 구한 후 모든 정점에서 2개의 치킨집 중 가장 가까운 치킨집을 구하여 그 시간을 모든 총 시간을 나타내는 시간에 더해주었고, 이렇게 모든 경우를 ..
알고리즘/백준_JAVA 2022. 1. 28. 13:56
이전 Prev 1 Next 다음