[코독하구만 팀] 2021.01.13(수) - 4주차 개인 결과

- 목표 -

codekodo.tistory.com/26

[코독하구만 팀] 2021.01.13(수) - 4주차 개인 목표

 

다익스트라란?

최단 경로를 탐색하는 알고리즘의 한 종류로 정점들 사이의 가중치를 비교하는 과정을 통해 최단 경로를 탐색한다.

 

해당 그림에서 정점과 간선의 가중치를 표로 나타내면 다음과 같다.

특정 행에서 특정 열로 이동할 때 발생하는 가중치를 나타낸 표이다.

인접하지 않은 경우 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