2학년 동계 모각코 2회차

목표 : 이것이 코딩 테스트다 with 파이썬 최단경로 공부 및 문제를 풀어보자.

최단경로 알고리즘은 그리디 알고리즘과 다이나믹 프로그래밍 알고리즘이 적용된다는 특징을 가지고 있다.

다익스트라 최단 경로 알고리즘

• 그래프에서 여러 개의 노드가 있을 때, 특정 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘
• 음의 간선이 없어야 정상적으로 동작
• 각 노드에 대한 현재까지의 최단 거리 정보를 항상 1차원 리스트에 저장하며 계속 갱신

1. 출발 노드를 설정
2. 최단 거리 테이블 초기화
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드 선택
4. 해당 노드를 거쳐 다른 노드로 가는 비용 계산하여 최단거리 테이블 갱신(그리디 알고리즘)
5. 위 과정에서 3,4 반복.

방법 1. 간단한 다익스트라 알고리즘

• 시간복잡도

  V = 노드의 개수

• Code

import sys
input = sys.stdin.readline
INF = int(1e9)

# 노드의 개수, 간선의 개수를 입력받기 n = 노드, m = 간선
n, m = map(int, input().split())
# 시작 노드 번호 입력받기
start = int(input())
# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트 graph
graph = [[] for i in range(n + 1)]
# 방문 여부 리스트 visited, False로 초기화
visited = [False] * (n + 1)
# 현재 상태의 거리 리스트 distance, INF로 초기화
distance = [INF] * (n + 1)

for _ in range(m):
    a, b, c = map(int, input().split())     # a 노드에서 b 노드의 비용이 c
    graph[a].append((b, c))

# 방문하지 않은 노드 중에서, 가장 최단 거리가 짧은 노드의 번호를 반환
def get_smallest_node():
    min_value = INF
    index = 0       # 가장 최단 거리가 짧은 노드(index)
    for i in range(1, n+1):
        if distance[i] < min_value and not visited[i]:
            min_value = distance[i]
            index = i
    return index

def dijkstra(start):
    # 시작 노드에 대해서 초기화
    distance[start] = 0
    visited[start] = True
    for j in graph[start]:
        distance[j[0]] = j[1]       # j에서 j[0]까지 가는 비용이 j[1]
    for i in range(n - 1):
        # 현재 최단 거리가 가장 짧은 노드를 방문 처리
        now = get_smallest_node()
        visited[now] = True
        # 현재 노드와 연결된 다른 노드를 확인
        for j in graph[now]:
            cost = distance[now] + j[1]
            # 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
            if cost < distance[j[0]]:
                distance[j[0]] = cost

dijkstra(start)

#모든 노드로 가기 위한 최단 거리 출력

for i in range(1, n + 1):
    # 도달 할 수 없는 경우, INF 출력
    if distance[i] == INF:
        print("INF")
    else:
        print(distance[i])

방법 2. 개선된 다익스트라 알고리즘

• 시간복잡도

  E 간선의 개수 V : 노드의 개수

• Code

import heapq
import sys

INF = int(1e9)  # 무한의 값 변수 설정

n, m = map(int,sys.stdin.readline().split())  #노드, 간선의 개수 입력받기

start = int(sys.stdin.readline())  # 시작 노드 입력받기

graph = [[] for i in range(n + 1)]  # 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트

distance = [INF] * (n + 1)  # 최단 거리 테이블 초기값 무한대로 설정

for _ in range(m):
    a, b, c = map(int, input().split()) # a 노드에서 b 노드로 가는 비용이 c
    graph[a].append((b,c))

def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))# 시작 노드로 가기 위한 최단 경로는 0으로 설정하여 큐에 삽입
    distance[start] = 0
    while q:
        dist, now = heapq.heappop(q)  # 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
        if distance[now] < dist:  # 현재 노드가 이미 처리된 적이 있는 노드라면 패스
            continue
        for i in graph[now]:    # 현재 노드와 연결된 다른 인접한 노드들 확인
            cost = dist + i[1] # 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))


dijkstra(start)

# 모든 노드로 가기 위한 최단 거리를 출력
for i in range(1, n + 1):
    if distance[i] == INF:
        print("INFINITY")
    else:
        print(distance[i])

플로이드 워셜 알고리즘 :

-모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에 사용할 수 있는 알고리즘
-노드의 개수가 N개일 때 알고리즘상으로 N번의 단계를 수행하며, 단계마다 N제곱의 연산을 통해 '현재 노드를 거쳐 가는' 모든 경로를 고려한다. 따라서 총 시간 복잡도는 N 세제곱이다.
Code

INF = int(1e9)
n = int(input())
m = int(input())

graph = [[INF] * (n + 1) for _ in range(n + 1)]  # 2차원 리스트를 만들고, 모든 값을 무한으로 초기화

#자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
for a in range(1, n + 1):
    for b in range(1, n + 1):
        if a == b:
            graph[a][b] = 0

# 각 간선에 대한 정보를 입력받아, 그 값으로 초기화
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a][b] = c

# 점화식에 따라 플로이드 워셜 알고리즘을 수행
for k in range(1, n + 1):
    for a in range(1, n + 1):
        for b in range(1, n + 1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

# 수행된 결과를 출력
for a in range(1, n + 1):
    for b in range(1, n + 1):
        #도달할 수 없는 경우, 무한으로 출력
        if graph[a][b] == INF:
            print("INFINITY", end=" ")
        else:
            print(graph[a][b], end= " ")
    print()

시간이 길어진 관계로 이론과 코드 이해까지만 하자...