다익스트라 (2) 썸네일형 리스트형 [백준] 11779번: 최소비용 구하기 2 - JAVA 🔗 문제 링크 BOJ 11779번: 최소비용 구하기 2 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 📝 풀이 과정 다익스트라로 + 경로를 구하는 문제이다. 다익스트라는 dist 배열을 통해 현재 노드에서부터 다음 노드로 이동하는 비용이 최소 비용이 될 때 갱신하는 방법을 사용하는데, 이 때 거리를 갱신하면서 현재 노드의 위치를 함께 저장하면 경로를 구할 수 있다. 만약, 1번에서 3번으로 이동했다면 3번 전에 1번 노드를 방문했다는 의미가 되고, prev[3] = 1가 되는 .. [백준] 1238번: 파티 - JAVA 🔗 문제 링크 BOJ 1238번: 파티 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 1️⃣ 플로이드-와샬 📝 풀이 과정 학생(i)가 이동하는 경로는 i -> X -> i이다. 따라서 이동하는데 걸리는 시간은 (i -> X) + (X -> i)이므로 학생마다 걸리는 시간을 모두 구할 수 있는 플로이드-와샬 알고리즘이 생각났다. ⏱ 시간 복잡도 플로이드 와샬의 경우 시간복잡도가 $O(N^3)$인데, 학생의 수는 최대 1000이므로 세제곱을 하여도 $10^9$ 이므로 1초이내에 해.. 이전 1 다음
