구름 개발일기장

🐢 다익스트라의 사용 Q. 다익스트라는 언제 사용하는 알고리즘일까? A. 시작점이 주어졌을때, 최소 비용으로 (혹은 최대 이익)으로 정점들을 거쳐서 다른 모든 정점까지 가는 비용을 알 수 있다. 🐢 기본 구조 // pair는 다음 노드로 가기위한 비용과 다음 노드의 정보가 들어있다 ArrayList[] adj = new ArrayList[N]; // dp는 현재 노드에서 특정 노드까지의 비용을 업데이트하기 위한 배열 int dp[N]; // 시작점을 제외한 모든 노드들에 대해 비용을 최대로 잡아준다, 시작점은 0 for (int i = 0; i < N; i++) dp[i] = INF; dp[S] = 0; adj 리스트 배열에 모든 간선들에 대해서 시작점을 기준으로 넣어준다 dp[i] == S부터 i까지의..