Development Artist

도입 백준 단계별 풀기 최단경로 세 번째 문제이다. 풀이 1. s(var_start)에서 시작하여 g(point_one), h(point_two)를 무조건 지나서 도착지 후보 x1(list_dest[0], x2(list_dest[1], ...를 가는데, 최단거리를 구하는 문제. 2. 그렇다면 [s->g->h->x1] or [s->h->g->x1] 의 최단거리를 구해서 두개 중 출발지점->도착지점의 최단거리라면 results에 저장해준다. 코드 from sys import stdin from heapq import heappush, heappop INF = 1e7 def dijkstra(start): heap = [] heappush(heap, [0, start]) # 시작 노드 최단 경로 0 shorte..

도입 백준 단계별 풀기 최단경로 두 번째 문제이다. 풀이 1. 다익스트라 알고리즘을 사용한다. def dijkstra 함수를 정의하고, 매개변수로 start 할 꼭짓점을 받는다. 2. 그래프 정보를 가지는 변수(mat_table)를 선언한다. 단방향이 아닌, 양방향이기 때문에, 두 줄에 걸쳐서 넣어준다(윗 그림). 다음은 예제1의 입력이 주어졌을 때, 실제 만들어지는 mat_table 이다(아랫 그림). 3. 출발 꼭짓점으로 부터 해당 꼭짓점 까지의 weight값을 저장할 변수(list_shortest_dist)를 dijkstra함수 내부에 선언을 하고, 해당 변수를 return 하게 한다. 4. 1, v1, v2 지점을 dijkstra 함수의 매개변수로 주고, 그것에 맞는 list_shortest_di..

도입 백준 단계별 풀기 최단경로 첫 번째 문제이다. 다익스트라 알고리즘 [출처 : 위키 백과] 풀이 1. 다익스트라 알고리즘 사용할 것이다. dijkstra 라는 함수를 정의하고, 매개변수로 시작점(var_start)을 받는다. 2. heapq 라이브러리를 사용한다. heap에는 방문할 vertex의 정보들이 들어있다. [최단거리, vertex]로 구성이 되어 있다. 3. mat_table은 vertex간 어떻게 연결되어 있는지 인덱스값을 그 값에 해당하는 vertex(var_u)라고 두고, 해당 vertex에 연결된 다른 vertex(var_v)와 가중치(var_w) 정보를 넣어둔다. 4. list_shortest_dist는 시작점 index를 제외한 다른 index 들의 값을 INF(무한:infini..