- 목표 -
[코독하구만 팀] 2021.01.13(수) - 4주차 개인 목표
목표 : 최단 경로를 탐색하는 알고리즘인 다익스트라 알고리즘의 개념을 정리하고 관련된 실습 문제 3문제를 풀어본다. 이후 백준에서 관련된 문제를 풀어봄으로써 이를 응용하는 법까지 학습
codekodo.tistory.com
다익스트라란?
최단 경로를 탐색하는 알고리즘의 한 종류로 정점들 사이의 가중치를 비교하는 과정을 통해 최단 경로를 탐색한다.
해당 그림에서 정점과 간선의 가중치를 표로 나타내면 다음과 같다.
특정 행에서 특정 열로 이동할 때 발생하는 가중치를 나타낸 표이다.
인접하지 않은 경우 INF, 방향성에 의해 도달할 수 없을 때는 X로 나타내었다.
| A(여기로) | B | C | D | E | F | |
| A(여기에서) | 0 | 10 | 15 | INF | INF | INF |
| B | X | 0 | INF | 12 | INF | 15 |
| C | X | INF | 0 | INF | 10 | INF |
| D | INF | X | INF | 0 | INF | 1 |
| E | INF | INF | X | INF | 0 | X |
| F | INF | X | INF | X | 5 | 0 |
(방문한 노드는 노란색으로 표시)
1. A와 인접한 B, C와의 최단 거리를 구한다.
| A | B | C | D | E | F |
| 0 | 10 | 15 | INF | INF | INF |
2. B와 인접한 D, F와의 최단 거리를 구한다.
| A | B | C | D | E | F |
| 0 | 10 | 15 | 22 | INF | 27 |
3. C와 인접한 E와의 최단 거리를 구한다.
| A | B | C | D | E | F |
| 0 | 10 | 15 | 22 | 25 | 27 |
4. D와 인접한 F와의 최단 거리를 구한다. (27에서 23으로 갱신)
| A | B | C | D | E | F |
| 0 | 10 | 15 | 22 | 25 | 23 |
5. F와 인접한 E와의 최단 거리를 구한다. (모든 정점을 방문)
| A | B | C | D | E | F |
| 0 | 10 | 15 | 22 | 25 | 23 |
1. 다익스트라
최소힙을 이용하였고 모든 정점을 방문하면 갱신 과정을 종료한다. 단순히 최단 경로의 값을 출력하는 것이 아닌 최단 경로 과정(?)을 출력해야 하므로 최단 경로로 갱신 될 때 방문하는 정점을 새로운 dict형 변수에 저장한다.
import heapq
def dijkstra(v_dic, v_list, V, E, src, dst):
INF = float('inf')
distance = {}
for i in range(V):
distance[v_list[i]] = INF
distance[src] = 0
queue = []
prev = {}
for i in range(V):
prev[v_list[i]] = []
found = {}
for i in range(V):
found[v_list[i]] = False
heapq.heappush(queue, [0, src])
while queue:
v = heapq.heappop(queue)
found[v[1]] = True
for node_weight in v_dic[v[1]]:
if (found[node_weight[0]]):
continue
if (distance[node_weight[0]] > distance[v[1]] + node_weight[1]):
distance[node_weight[0]] = distance[v[1]] + node_weight[1]
heapq.heappush(queue, [distance[node_weight[0]], node_weight[0]])
prev[node_weight[0]] = [v[1], node_weight[0], node_weight[1]]
return prev
def main():
V, E = map(int, input().split())
v_list = input().split()
v_dic = {}
for i in v_list:
v_dic[i] = []
for _ in range(E):
i, j, c = input().split()
c = int(c)
v_dic[i].append([j,c])
src, dst = input().split()
prev = dijkstra(v_dic, v_list, V, E, src, dst)
prev_list = []
prev_e = dst
while prev_e != src:
prev_list.append(prev[prev_e])
prev_e = prev[prev_e][0]
prev_list.reverse()
for i in prev_list:
print(*i)
if __name__ == "__main__":
main()
2. 벨만 포드
다익스트라와 같은 최단 경로를 탐색하는 알고리즘이다. 하지만 다익스트라와의 차이점은 다익스트라는 음의 가중치가 없고 벨만 포드는 음의 가중치가 주어진다는 점이다. 해결 과정은 비슷하다. 벨만 포드의 경우 (정점의 수 - 1) 까지 탐색을 하고 이후 한번 더 탐색을 진행한다. 이 때 최단 거리가 갱신되는 값이 있으면 음의 루프가 존재한다는 의미이므로 문제에서 주어진 Negative Cycle!을 출력한다.
import heapq
def bellman_ford(v_dic, v_list, V, E, src, dst):
INF = float('inf')
distance = {}
for i in v_list:
distance[i] = INF
distance[src] = 0
predecessor = {}
for i in v_list:
predecessor[i] = None
for i in range(V-1):
for i in v_dic:
for j, c in v_dic[i]:
if distance[j] > distance[i] + c:
distance[j] = distance[i] + c
predecessor[j] = [i, j, c]
for i in v_dic:
for j, c in v_dic[i]:
if distance[j] > distance[i] + c:
return -1
return predecessor
def main():
V, E = map(int, input().split())
v_list = input().split()
v_dic = {}
for i in v_list:
v_dic[i] = []
for _ in range(E):
i, j, c = input().split()
c = int(c)
v_dic[i].append([j,c])
src, dst = input().split()
predecessor = bellman_ford(v_dic, v_list, V, E, src, dst)
if predecessor == -1:
print("Negative Cycle!")
else:
prev_list = []
prev_e = dst
while prev_e != src:
prev_list.append(predecessor[prev_e])
prev_e = predecessor[prev_e][0]
prev_list.reverse()
for i in prev_list:
print(*i)
if __name__ == "__main__":
main()
3. 경찰서
다익스트라를 활용한다. 시작 정점과 도착 정점을 (A, A) ~ (F, F)로 놓고 모든 경우를 탐색하고 이 값이 주어진 거리보다 작은 경우 새로운 dict형 변수에 저장한다. 이 과정이 종료되고 dict형 변수의 크기를 비교해서 이 값이 가장 큰 정점이 경찰이 다다를수 있는 지점이 가장 많은 정점이다.
import heapq
def dijkstra(v_dic, v_list, V, E, src, dst):
INF = float('inf')
distance = {}
for i in range(V):
distance[v_list[i]] = INF
distance[src] = 0
queue = []
prev = {}
for i in range(V):
prev[v_list[i]] = []
found = {}
for i in range(V):
found[v_list[i]] = False
heapq.heappush(queue, [0, src])
while queue:
v = heapq.heappop(queue)
found[v[1]] = True
for node_weight in v_dic[v[1]]:
if (found[node_weight[0]]):
continue
if (distance[node_weight[0]] > distance[v[1]] + node_weight[1]):
distance[node_weight[0]] = distance[v[1]] + node_weight[1]
heapq.heappush(queue, [distance[node_weight[0]], node_weight[0]])
prev[node_weight[0]] = [v[1], node_weight[0], node_weight[1]]
return distance[dst]
def main():
V, E = map(int, input().split())
v_list = input().split()
v_dic = {}
for i in v_list:
v_dic[i] = []
for _ in range(E):
i, j, c = input().split()
c = int(c)
v_dic[i].append([j,c])
v_dic[j].append([i,c])
len_dic = {}
for i in v_list:
len_dic[i] = []
min_len = int(input())
for i in v_list:
for j in v_list:
result = dijkstra(v_dic, v_list, V, E, i, j)
if min_len >= result:
len_dic[i].append(result)
len_dic[j].append(result)
result = []
for i in range(len(len_dic)):
result.append([v_list[i],len_dic[v_list[i]]])
result = sorted(result, key = lambda x : len(x[1]))
print(result[len(result)-1][0], int(len(result[len(result)-1][1])//2))
if __name__ == "__main__":
main()
- 깃허브 -
github.com/k906506/2020_Winter_Assemble-And-selfcode
k906506/2020_Winter_Assemble-And-selfcode
Contribute to k906506/2020_Winter_Assemble-And-selfcode development by creating an account on GitHub.
github.com
'⛹️ 라이프 > 2020 겨울방학 모각코(개인)' 카테고리의 다른 글
| [코독하구만 팀] 2021.01.20(수) - 5주차 개인 결과 (0) | 2021.01.22 |
|---|---|
| [코독하구만 팀] 2021.01.20(수) - 5주차 개인 목표 (0) | 2021.01.20 |
| [코독하구만 팀] 2021.01.13(수) - 4주차 개인 결과 (0) | 2021.01.13 |
| [코독하구만 팀] 2021.01.13(수) - 4주차 개인 목표 (0) | 2021.01.13 |
| [코독하구만 팀] 2020.01.05(화) - 3주차 개인 결과 (0) | 2021.01.05 |
| [코독하구만 팀] 2021.01.05(화) - 3주차 개인 목표 (0) | 2021.01.05 |