룰루랄라 알고리즘

한창 타임머신에 관해 연구하고 있던 찰나에 나의 흥미를 돋우는 제목의 문제를 발견했다. 해당 문제를 풀면서 graph를 class Node를 이용해 구성하였다. 특이점은 Node에 출발점, 도착점, 가중치를 모두 선언하지 않고 도착점, 가중치만 구성하여서 해당 Node가 있는 index가 출발점 역할을 하도록 했다. 처음에는 파이썬에서의 버릇 때문에 위와 같이 구성했는데 생각해 보면 만약 한 정점에서만 출발하는 간선이 많을 경우 비효율 적으로 예상됨에 따라 Node에 출발점, 도착점, 가중치를 모두 선언하고 하나의 ArrayList에 선언하는 것도 좋을 것 같다. 또 벨만-포드 알고리즘에서 왜 V-1번만 반복해야 하는지 의문을 해소하지 못했다. https://www.acmicpc.net/problem/1..

정점의 개수 V, 간선의 개수 E, 목적지 후보의 개수 W 출발지 s, 정점 g와 h 사이를 지나감 목적지 후보 stack[] 1. 양방향 노선인 간선의 정보 저장 2. 다익스트라 알고리즘을 이용하여 시작점이 s,g,t인 distance를 각각 distart, dig, dih에 저장 **함수에서 리스트 자체를 리턴하여 저장 할 수 있다!! **리스트를 리턴하지 않고 값을 하나하나 리턴한다면 수많은 다익스트라를 수행 해야 해서 시간초과에 걸릴 수 밖에 없음 3. 목적지 후보까지의 최단 경로는 s->g->h->목적지 후보, s->h->g->목적지 후보 두 가지이므로 목적지와 경로가 같다면 result에 저장 4. 오름차순 정렬하여 출력

정점의 개수 V, 간선의 개수 E 반드시 거쳐야 하는 정점 n1,n2 1. 양방향이므로 graph[u].append([w,v]), graph[v].append([w,u]) 2. 다익스트라 알고리즘 수행 3. n1과 n2를 반드시 거쳐야 하므로 u->n1->n2->v, u->n2->n1->v 두 가지 경로가 있음 4. 결과에 두 가지 경로중 작은 값을 저장

정점의 개수 V, 간선의 개수 E 1. distance 거리 INF로 초기화 2. 2차원 배열 graph를 이용해 간선의 정보 저장 3. 시작 노드로 가기 위한 최단 경로는 0으로 초기화 하여 heap에 삽입 4. 다익스트라 알고리즘 수행 5. 여전히 거리가 INF라면 경로가 없는 것이므로 INF출력 6. 그렇지 않다면 최단 경로 출력