[ 프로그래머스 ] #12978 : 배달 - JAVA

🔗 배달import java.util.*;class Solution { public int solution(int N, int[][] road, int K) { // 그래프를 인접 리스트 형태로 초기화 List> graph = new ArrayList(); for (int i = 0; i ()); } for (int[] r : road) { int a = r[0], b = r[1], c = r[2]; graph.get(a).add(new int[] { b, c });//도착 노드, 시간 graph.get(b).add(new int[] { a, c }); } ..

• format_list_bulleted 코딩테스트/문제풀이
• · 2025. 1. 9.
• textsms

[ 알고리즘 ] Dijkstra Algorithm

시작 노드에서 다른 모든 노드까지의 최단 경로를 찾는 알고리즘⚠️ 음의 가중치를 가지지 않는 그래프에서만 동작(음의 가중치 → Bellman-Ford Algorithm)🔎 핵심그래프 : edge에는 weight(가중치) 존재최단 경로탐욕 알고리즘 기반 : 현재 가장 비용이 적은 경로를 우선적 탐색🔎 Flow초기화시작 노드의 최단 거리 = 0나머지 모든 노드의 거리 = ∞방문하지 않은 노드 배열(or 우선순위 큐 생성)방문 처리최단 거리 업데이트 필요 없는 노드는 방문 완료로 처리방문하지 않은 노드 중 최단 거리가 가장 작은 노드를 선택해 탐색최단 거리 업데이트현재 노드에서 연결된 인접 노드들의 최단 거리 계산 → 기존의 최단 거리보다 작다면 갱신모든 노드를 방문할 때까지 반복🔎 배열import ja..

• format_list_bulleted 코딩테스트/개념정리
• · 2025. 1. 8.
• textsms