7. 최단 경로 (다익스트라, 플로이드 워셜 알고리즘)

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

- 다익스트라 (Dijkstra) 최단 경로 알고리즘은 그래프에서 여러 개의 노드가 있을 떄, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다.

=> '음의 간선'이 없을 때 정상적으로 동작한다.

=> 따라서, 실제로 GPS 소프트웨어의 기본 알고리즘으로 채택되곤 한다.

 

- 다익스트라 알고리즘은 일반적으로 그리디 알고리즘으로 분류된다.

=> 매번 '가장 비용이 적은 노드'를 선택해서 임의의 과정을 반복하기 때문이다.

 

(1) 다익스트라 알고리즘의 간략한 원리

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

- 매번 현재 처리하고 있는 노드를 기준으로 주변 간선을 확인한다. 나중에 현재 처리하고 있는 노드와 인접한 노드로 도달하는 더 짧은 경로를 찾으면 '더 짧은 경로도 있었네? 이제부터는 이 경로가 제일 짧은 경로야'라고 판단한다.

 

(2) 힙 설명

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

 

- 우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제한다는 점이 특징이다.

 

- 우선순위 큐를 힙을 통해 구현할 때는, 내부적으로 최소 합(Min Heap) 혹은 최대 힙(Max Heap)을 이용한다. 최소 힙을 이용하는 경우 '값이 낮은 데이터가 먼저 삭제'되며, 최대 힙을 이용하는 경우 '값이 큰 데이터가 먼저 삭제'된다.

=> 파이썬 라이브러리 heapq에서는 기본적으로 최소 힙 구조를 이용한다.

=> 최대 힙 구조를 이용하기 위해서는 음수 부호를 붙이면 된다.

 

- 힙을 통해 우선순위 큐를 구현하면 삽입시간과 삭제 시간이 모두 O(logN)이다.

 

(3) 개선된 다익스트라 알고리즘

- 시간 복잡도 O(ElogV)를 보장한다. (이 때, V는 노드의 개수이고, E는 간선의 개수를 의미한다)

- 힙 자료구조를 이용해서 우선순위 큐를 사용한다.

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

n,m = map(int,input().split())

start = int(input())

graph = [[] for _ in range(n+1)]

distance = [INF] * (n+1)

for _ in range(m):
    a,b,c = map(int,input().split())
    graph[a].append((b,c))

def dijkstra(start):
    q = []
    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 = i[1] + dist

            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])

 

 

 

2. 플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm)

- 플로이드 워셜 알고리즘은 '모든 지점에서 다른 모든 지점까지의 최단 경로를 모드 구해야 하는 경우'에 사용할 수 있는 알고리즘이다.

- 총 시간 복잡도는 O(N^3)이다.

- 2차원 리스트에 최단 거리 정보를 저장한다는 특징이 잇다.

- 다이나믹 프로그래밍에 속한다.

- 해당 알고리즘에서는 현재 확인하고 있는 노드를 제외하고, N-1개의 노드 중에서 서로 다른 노드 (A,B)쌍을 선택한다. 이후에 A-> 1번 노드 -> B로 가는 비용을 확인한 뒤에 최단 거리를 갱신한다.

=> Dab = min(Dab, Dak+Dkb)

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

n,m = map(int,input().split())

graph = [[INF]*(n+1) for _ in range(n+1)]

for a in range(1,n+1):
    graph[a][a] = 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()

 

3. 문제

(1) 미래 도시

※ 문제는 생략

 

<입력 조건>

• 방문 판매원 A는 현재 1번에 있으며, 1에서 K번 회사를 방문한 후, X번 회사로 가는 것이 목표이다.
• 첫째 줄에 전체 회사의 개수 N과 경로의 개수 M이 공백으로 구분되어 차례대로 주어진다. (1<=N,M<=100)
• 둘쨰 줄부터 M+1번째 줄에는 연결된 두 회사의 번호가 공백으로 구분되어 주어진다.
• M+2번째 줄에는 X와 K가 공백으로 구분되어 차례로 주어진다. (1<=K<=100)
• 모든 도로의 이동 시간은 1이다.

<출력 조건>

• 첫째 줄에 K번 회사를 거쳐 X번 회사로 가는 최소 이동 시간을 출력한다.
• 만약 X번 회사에 도달할 수 없다면 -1을 출력한다.

입력 예시 1 5 7 1 2 1 3 1 4 2 4 3 4 3 5 4 5 4 5

출력 예시1 3

입력 예시 2 4 2 1 3 2 4 3 4

출력 예시2 -1

* 플로이드 워셜 알고리즘 사용!

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

n,m = map(int,input().split())

graph = [[INF]*(n+1) for _ in range(n+1)]

for a in range(1,n+1):
    graph[a][a] = 0

for _ in range(m):
    a,b = map(int,input().split())
    graph[a][b] = 1
    graph[b][a] = 1

x,k = map(int,input().split())

for t 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][t]+graph[t][b])

answer = graph[1][k]+graph[k][x]

if answer >= INF:
    answer = -1

print(answer)

 

 

(2) 전보

※ 문제 생략

 

<입력 조건>

• 첫째 줄에 도시의 개수 N, 통로의 개수 M, 메세지를 보내고자 하는 도시 C가 주어진다.
• (1 <= N <= 30,000, 1 <= M <= 200,000, 1<=C<=N)
• 둘째 줄부터 M+1번째 줄에 걸쳐서 통로에 대한 정보 X,Y,Z가 주어진다. 이는 특정 도시 X에서 다른 특정 도시 Y로 이어지는 통로가 있으며, 메시지가 전달되는 시간이 Z라는 의미다.
• (1 <= X,Y <= N, 1 <= X <= 1,000)

<출력 조건>

• 첫째 줄에 도시 C에서 보낸 메시지를 받는 도시의 총 개수와 총 걸리는 시간을 공백으로 구분하여 출력한다.

* 다익스트라 알고리즘 사용!

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

n,m,c = map(int,input().split())

graph = [[] for _ in range(n+1)]
distance = [INF] * (n+1)

for _ in range(m):
    x,y,z = map(int,input().split())
    graph[x].append((y,z))

def dijkstra(start):
    q = []
    heapq.heappush(q,(0,start))
    distance[start] = 0

    while q:
        dist, now = heapq.heappop(q)

        if distance[now] == INF:
            continue

        for i in graph[now]:
            cost = dist + i[1]

            if distance[i[0]] > cost:
                distance[i[0]] = cost
                heapq.heappush(q,(cost,i[0]))

dijkstra(c)

counts = [i for i in distance if i != INF]

print(len(counts)-1, max(counts))

 

 

 

(3) 플로이드

https://www.acmicpc.net/problem/11404

11404번: 플로이드

* 플로이드 워셜 알고리즘 사용

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

n = int(input().rstrip())
m = int(input().rstrip())

graph = [[INF] * (n+1) for _ in range(n+1)]

for a in range(1,n+1):
    graph[a][a] = 0

for _ in range(m):
    a,b,c = map(int, input().rstrip().split())
    graph[a][b] = min(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(0, end =' ')
        else:
            print(graph[a][b], end = ' ')
    
    print()

 

 

 

(4) 정확한 순위

- 선생님은 시험을 본 학생 N명의 성적을 분실하고, 성적을 비교한 결과의 일부만 가지고 있습니다. 학생 N명의 성적은 모두 다른데, 다음은 6명의 학생에 대하여 6번만 성적을 비교한 결과입니다.

• 1번 학생의 성적 < 5번 학생의 성적
• 3번 학생의 성적 < 4번 학생의 성적
• 4번 학생의 성적 < 2번 학생의 성적
• 4번 학생의 성적 < 6번 학생의 성적
• 5번 학생의 성적 < 2번 학생의 성적
• 5번 학생의 성적 < 4번 학생의 성적

위를 통해 유추해서 순위를 정확히 알 수 있는 학생도 있고, 알 수 없는 학생도 있습니다. 예를 들어 1번 학생은 5번 학생보다 성적이 낮고, 5번 학생은 4번 학생보다 성적이 낮으므로 1번 학생은 4번 학생보다 성적이 낮습니다. 따라서 1번, 3번, 5번 학생은 모두 4번 학생보다 성적이 낮다고 볼 수 있습니다. 그리고 4번 학생은 2번 학생과 6번 학생보다 성적이 낮습니다. 정리하면 4번 학생보다 성적이 낮은 학생은 3명이고, 성적이 높은 학생은 2명이므로 4번 학생의 성적 순위를 정확히 알 수 있습니다. 하지만 예시에서 4번 학생을 제외한 다른 학생은 정확한 순위를 알 수 없습니다.

학생들의 성적을 비교한 결과가 주어질 때, 성적 순위를 저확히 알 수 있는 학생은 모두 몇 명인지 계산하는 프로그램을 작성하세요.

 

<입력 조건>

• 첫째 줄에 학생들의 수 N(2 <= N <= 400)과 두 학생의 성적을 비교한 횟수 M(2 <= M <= 10,000)이 주어집니다.
• 다음 M개의 각 줄에는 두 학생의 성적을 비교한 결과를 나타내는 두 양의 정수 A와 B가 주어집니다. 이는 A번 학생의 성적이 B번 학생보다 낮다는 것을 의미합니다.

<출력 조건>

• 첫째 줄에 성적 순위를 정확히 알 수 있는 학생이 몇 명인지 출력합니다.

입력 예시 6 6 1 5 3 4 4 2 4 6 5 2 5 4

출력 예시 1

* 플로이드 워셜 알고리즘 사용!

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

n,m = map(int, input().rstrip().split())

graph = [[INF] * (n+1) for _ in range(n+1)]

for a in range(1,n+1):
    graph[a][a] = 0

for _ in range(m):
    a,b = map(int, input().rstrip().split())
    graph[a][b] = 1

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])

answer = 0

for i in range(1,n+1):
    count = 0
    for j in range(1,n+1):
        if graph[j][i] != INF or graph[i][j]!=INF:
            count += 1
    
    if count == n-1:
        answer += 1

print(answer)

 

 

 

(5) 화성 탐사

- 당신은 화성 탐사 기계를 개발하는 프로그래머입니다. 그런데 화성은 에너지 공급원을 찾기가 힘듭니다. 그래서 에너지를 효율적으로 사용하고자 화성 탐사 기계가 출발 지점에서 목표 지점까지 이동할 때 항상 최적의 경로를 찾도록 개발해야 합니다.

화성 탐사 기계가 존재하는 공간은 N x N 크기의 2차원 공간이며, 각각의 칸을 지나기 위한 비용(에너지 소모량)이 존재합니다. 가장 왼쪽 위 칸인 [0][0] 위치에서 가장 오른쪽 아래 칸인 [N -1][N-1] 위치로 이동하는 최소 비용을 출력하는 프로그램을 작성하세요. 화성 탐사 기계는 특정한 위치에서 상하좌우 인접한 곳으로 1칸씩 이동할 수 있습니다.

 

<입력 조건>

• 첫째 줄에 테스트 케이스의 수 T(1 <= T <= 10)가 주어집니다.
• 매 테스트 케이스의 첫째 줄에는 탐사 공간의 크기를 의미하는 정수 N이 주어집니다. (2 <= N <= 125)
• 이어서 N 개의 줄에 걸쳐 각 칸의 비용이 주어지며 공백으로 구분합니다. () <= 각 칸의 비용 <= 9)

<출력 조건>

• 각 테스트 케이스마다 [0][0]의 위치에서 [N -1][N - 1]의 위치로 이동하는 최소 비용을 한 줄에 하나씩 출력합니다.

입력 예시 3 3 5 5 4 3 9 1 3 2 7 5 3 7 2 0 1 2 8 0 9 1 1 2 1 8 1 9 8 9 2 0 3 6 5 1 5 7 9 0 5 1 1 5 3 4 1 2 1 6 5 3 0 7 6 1 6 8 5 1 1 7 8 3 2 3 9 4 0 7 6 4 1 5 8 3 2 4 8 3 7 4 8 4 8 3 4

출력 예시 20 19 36

* 다익스트라 사용

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

t = int(input().rstrip())

def dijkstra(graph, n):
    distance = [[INF]*(n) for _ in range(n)]
    q = []
    heapq.heappush(q,(graph[0][0], 0, 0))
    distance[0][0] = graph[0][0]
    move = [(0,1),(0,-1),(1,0),(-1,0)]

    while q:
        dist, nowy, nowx = heapq.heappop(q)

        if distance[nowy][nowx] < dist:
            continue

        for my,mx in move:
            ny = nowy+my
            nx = nowx+mx

            if ny<0 or ny>=n or nx<0 or nx>=n:
                continue

            cost =dist + graph[ny][nx]
            if distance[ny][nx]>cost:
                distance[ny][nx] = cost
                heapq.heappush(q,(cost,ny,nx))

    return distance[n-1][n-1]



for _ in range(t):
    n = int(input().rstrip())
    graph = []

    for _ in range(n):
        graph.append(list(map(int,input().rstrip().split())))

    print(dijkstra(graph,n))

 

 

 

(6) 숨바꼭질

- 동빈이는 숨바꼭질을 하면서 술래로부터 잡히지 않도록 숨을 곳을 찾고 있습니다. 동빈이는 1 ~ N번까지의 헛간 중에서 하나를 골라 숨을 수 있으며, 술래는 항상 1번 헛간에서 출발합니다. 전채 맵에는 총 M개의 양방향 통로가 존재하며, 하나의 통로는 서로 다른 두 헛간을 연결합니다. 또한 전체 맵은 항상 어떤 헛간에서 다른 어떤 헛간으로 도달이 가능한 형태로 주어집니다.

동빈이는 1번 헛간으로부터 최단 거리가 가장 먼 헛간이 가장 안전하다고 판단하고 있습니다. 이때 최단거리의 의미는 지나야 하는 길의 최소 개수를 의미합니다. 동빈이가 숨을 헛간의 번호를 출력하는 프로그램을 작성하세요.

 

<입력 조건>

• 첫째 줄에는 N과 M이 주어지며, 공백으로 구분합니다. (2 <= N <= 20,000), (1 <= M <= 50,000)
• 이후 M개의 줄에 걸쳐서 서로 연결된 두 헛간 A와 B의 번호가 공백으로 구분되어 주어집니다. (1 <= A,B <= N)

<출력 조건>

• 첫 번째는 숨어야 하는 헛간 번호를(만약 거리가 같은 헛간이 여러개면 가장 작은 헛간 번호를 출력합니다), 두 번쨰는 그 헛간 까지의 거리를, 세 번쨰는 그 헛간과 같은 거리를 갖는 헛간의 개수를 출력해야 합니다.

입력 예시 6 7 3 6 4 3 3 2 1 3 1 2 2 4 5 2

출력 예시 4 2 3

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

n,m = map(int, input().rstrip().split())

graph = [[] for _ in range(n+1)]

for _ in range(m):
    a,b = map(int,input().rstrip().split())
    graph[a].append(b)
    graph[b].append(a)

distance = [INF] * (n+1)


def dijkstra():
    q = []
    heapq.heappush(q,(0,1))
    distance[1] = 0

    while q:
        dist, now = heapq.heappop(q)

        if distance[now] < dist:
            continue

        for i in graph[now]:
            cost = dist + 1

            if cost < distance[i]:
                distance[i] = cost
                heapq.heappush(q,(cost,i))

dijkstra()

max_dist = -1

for i in range(1,n+1):
    if distance[i] != INF and distance[i] > max_dist:
        max_dist = distance[i]

number = distance.index(max_dist)
count = distance.count(max_dist)

print(number, max_dist, count)