이코테 강의 몰아보기 | 7. 다이나믹 프로그래밍

 

[1] 최단 경로 알고리즘

 

1. 최단 경로 문제

: 가장 짧은 경로를 찾는 알고리즘을 의미한다.

 

1-1. 최단경로 다양한 문제

- 한 지점에서 다른 한 지점까지의 최단 경로

- 한 지점에서 모든 지점까지의 최단 경로

- 모든 지점에서 다른 모든 지점까지의 최단 경로

 

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

: 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산한다.

- 다익스트라 최단 경로 알고리즘은 음의 간선(도로)인 없을 때 정상적으로 동작한다.

- 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복

 

2-1. 다익스트라 최단 경로 알고리즘 동작 과정

1) 출발 노드를 설정한다.

2) 최단 거리 테이블을 초기화한다.

3) 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.

4) 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.

5) 위 과정에서 3번과 4번을 반복한다.

 

2-2. 특징

- 그리디 알고리즘에 속한다. 

* 그리디 알고리즘 : 매 상황에서 방무낳지 않은 가장 비용이 적은 노드를 선택해 임의의 과정을 반복

- 단계를 거치며 한 번 처리된 노드의 최단 거리는 고정되어 더 이상 바뀌지 않는다.

- 다익스트라 알고리즘을 수행한 뒤에 테이블에 각 노드까지의 최단 거리 정보가 저장된다.

 

3. 계선된 다익스트라 알고리즘

: 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해 힙(Heap) 자료구조를 이용한다.

 

3-1. 우선순위 큐(Priority Queue)

: 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조이다.

예를 들어 여러 개의 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건 데이터부터 꺼내서 확인해야 하는 경우에 우선순위 큐를 이용할 수 있다.

대부분의 프로그래밍 언어에서 표준 라이브러리 형태로 지원한다.

 

3-2. 힙(Heap)

: 우선순위 큐를 구현하기 위해 사용하는 자료구조 중 하나이다.

- 최소 힙(Min Heap)과 최대 힙(Max Heap)이 있다.

 

# 최소힙

import heapq

# 오름차순 힙 정렬(Heap Sort)
def heapsort(iterable):
    h = []
    result = []
    # 모든 원소를 차례대로 힙에 삽입
    for vlaue in iterable:
        heapq.heappush(h, vlaue)
    #힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
    for i in range(len(h)):
        result.append(heapq.heappop(h))
    return result

result = heapsort([1,3,5,7,9,2,4,6,8,0])
print(result)

# 실행결과
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

#최대힙

#최대 힙
import heapq

# 내림차순 힙 정렬(Heap Sort)
def heapsort(iterable):
    h = []
    result = []
    # 모든 원소를 차례대로 힙에 삽입
    for value in iterable:
        heapq.heappush(h, -value)
    # 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
    for i in range(len(h)):
        result.append(-heapq.heappop(h))
    return result

result = heapsort([1,3,5,7,9,2,4,6,8,0])
print(result)

#실행 결과
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

 

4. 플로이드 워셜 알고리즘

: 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다.

- 다익스트라 알고리즘과 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 알고리즘을 수행한다.

다만, 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾는 과정이 필요하지 않는다.

- 2차원 테이블에 최단거리 정보를 저장한다.

 

5. 실전문제 풀이

#page262. 전보

아이디어 : 한 도시에서 다른 도시가지의 최단 거리 문제로 치환할 수 있다.

N과 M의 범위가 충분히 크기 때문에 우선순위 큐를 활용한 다익스트라 알고리즘을 구현한다.

 

import heapq

INF = int(1e9) #무한을 의미하는 값으로 10억을 설정

def dijkstra(start):
    q = []
    #시작 노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입
    heapq.heappush(q, (0, start))
    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]))


# 노드의 개수, 간선의 개수, 시작 노드를 입력 받기
n, m, start = map(int, input().split())
# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기
graph = [[] for i in range(n+1)]
# 최단 거리 테이블을 모두 무한으로 초기화
distance = [INF] * (n+1)

# 모든 간선 정보를 입력 받기
for _ in range(m):
    x, y, z = map(int, input().split())
    # X번 노드에서 Y번 노드로 가는 비용이 Z라는 의미
    graph[x].append((y, z))

# 다익스트라 알고리즘을 수행
dijkstra(start)

#도달할 수 있는 노드의 개수
count = 0
# 도달할 수 있는 노드 중에서, 가장 멀리 있는 노드와의 최단 거리
max_distance = 0
for d in distance:
    #도달할 수 있는 노드인 경우
    if d != 1e9:
        count += 1
        max_distance = max(max_distance, d)

# 시작 노드는 제외해야 하므로 count - 1을 출력
print(count-1, max_distance)

 

 

#page.259 미래 도시

아이디어 : 전형적인 최단 거리 문제이므로 최단 거리 알고리즘을 이용하여 해결한다.

N의 크기가 최대 100이므로 플로이드 워셜 알고리즘을 이용해도 효율적으로 해결할 수 있다.

플로이드 워셜 알고리즘을 수행한 뒤에 (1번 노드에서 X까지의 최단 거리 + X에서 K까지의 최단 거리)를 계산하여 출력하면 정답 판정을 받을 수 있다.

 

INF = int(1e9) #무한을 의미하는 값으로 10억을 설정

#노드의 개수 및 간선의 개수를 입력받기
n,m = map(int, input().split())
#2차원 리스트(그래프 표현)를 만들고, 모든 값을 무한으로 초기화
graph = [[INF] * (n+1) for _ in range(n+1)]

#자기 자신에서 자기 자신으로 가는 비용은 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가 서로에게 가는 비용은 1이라고 설정
    a,b = map(int, input().split())
    graph[a][b] = 1
    graph[b][a] = 1

#거쳐 갈 노드 x와 최종 목적지 노드 k를 입력받기
x,k = map(int,input().split())

#점화식에 따라 플로이드 워셜 알고리즘 수행
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])

#수행된 결과를 출력
distance = graph[1][k] + graph[k][x]

#도달할 수 없는 경우, -1을 출력
if distance >= INF:
    print("-1")

#도달할 수 있다면, 최단 거리를 출력
else:
    print(distance)