8 분 소요

특정한 최단 경로

solved_ac[Class4] 특정한 최단 경로

문제

방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.

세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v1과 v2가 주어진다. (v1 ≠ v2, v1 ≠ N, v2 ≠ 1) 임의의 두 정점 u와 v사이에는 간선이 최대 1개 존재한다.

출력

첫째 줄에 두 개의 정점을 지나는 최단 경로의 길이를 출력한다. 그러한 경로가 없을 때에는 -1을 출력한다.

예제 입력 1

4 6
1 2 3
2 3 3
3 4 1
1 3 5
2 4 5
1 4 4
2 3

예제 출력 1

7

문제 해석

최단 경로 문제

  • 최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘을 의미
  • 다양한 문제 상황
    • 한 지점에서 다른 한 지점까지의 최단 경로
    • 한 지점에서 다른 모든 지점까지의 최단 경로
    • 모든 지점에서 다른 모든 지점까지의 최단 경로
  • 각 지점은 그래프에서 노드로 표현
  • 지점 간 연결된 도로는 그래프에서 간선으로 표현

image

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

  • 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산
  • 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작
    • 현실 세계의 도로(간선)은 음의 간선으로 표현되지 않는다.
  • 다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류된다.
    • 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복

      동작 과정

  1. 출발 노드를 설정한다.
  2. 최단 거리 테이블을 초기화한다.
  3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
  4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신
  5. 위 과정에서 3번과 4번 반복
  • 알고리즘 동작 과정에서 최단 거리 테이블은 각 노드에 대한 현재까지의 최단 거리 정보를 가지고 있다.
  • 처리 과정에서 더 짧은 경로를 찾으면 ‘이제부터는 이 경로가 제일 짧은 경로야’라고 갱신한다.

image

image

초기 상태

image

  • [Step 1] 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드인 1번 노드를 처리한다.

image

  • [Step 2] 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드인 4번 노드를 처리한다.

image

  • [Step 3] 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드인 2번 노드를 처리한다.

image

  • [Step 4] 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드인 5번 노드를 처리한다.

image

  • [Step 5] 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드인 3번 노드를 처리한다.

image

  • [Step 6] 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드인 6번 노드를 처리한다.

image

특징

  • 그리디 알고리즘 : 매 상황에서 방문하지 않은 가장 비용이 적은 노드를 선택해 임의의 과정을 반복
  • 단계를 거치며 한 번 처리된 노드의 최단 거리는 고정되어 더 이상 바뀌지 않는다.
    • 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는 것으로 이해할 수 있다.
  • 다익스트라 알고리즘을 수행한 뒤에 테이블에 각 노드까지의 최단 거리 정보가 저장됨.
    • 완벽한 형태의 최단 경로를 구하려면 소스코드에 추가적인 기능을 더 넣어야함.

간단한 구현 방법

  • 단계마다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해 매 단계마다 1차원 테이블의 모든 원소를 확인(순차 탐색)한다.

예제 코드(최소 힙 사용 x)

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

n, m = map(int, sys.stdin.readline().split())

start = int(sys.stdin.readline())

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

visited = [False] * (n + 1)

distance = [INF] * (n + 1)

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

def get_smallest_node():
    min_value = INF
    index = 0
    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]

    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):
    if distance[i] == INF:
        print("INFINITY")
    else:
        print(distance[i])
  • 총 O(V)번에 걸쳐서 최단 거리가 가장 짧은 노드를 매번 선형 탐색해야 한다.
  • 따라서 전체 시간 복잡도는 O(V^2)이다.
  • 일반적으로 코딩 테스트의 최단 경로 문제에서 전체 노드의 개수가 5000개 이하라면 이 코드로 문제를 해결할 수 있다.
    • 하지만 노드의 개수가 10000개를 넘어가는 문제라면??

예제 코드(최소 힙(우선순위 큐) 사용)

  • 자료구조
    1. 스택 - 가장 나중에 삽입된 데이터 추출
    2. 큐 - 가장 먼저 삽입된 데이터 추출
    3. 우선순위 큐 - 가장 우선순위가 높은 데이터 추출
  • 리스트
    • 삽입 시간
      • O(1)
    • 삭제 시간
      • O(N)
  • 힙
    • 삽입 시간
      • O(logN)
    • 삭제 시간
      • O(logN)

힙에 대해서는 1927번: 최소 힙에서 자세히 다루니 참고하도록 하자.

  • 단계마다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해 힙 자료구조를 이용
  • 다익스트라 알고리즘이 동작하는 기본 원리는 동일
    • 현재 가장 가까운 노드를 저장해 놓기 위해서 힙 자료구조를 추가적으로 이용
    • 현재의 최단 거리가 가장 짧은 노드를 선택해야 하므로 최소 힙 사용
  • [초기 상태] 그래프를 준비하고 출발 노드를 설정하여 우선순위 큐에 삽입

image

  • [Step 1] 우선순위 큐에서 원소를 꺼냄. 1번 노드는 아직 방문하지 않았으므로 이를 처리

image

  • [Step 2] 우선순위 큐에서 원소를 꺼냄. 4번 노드는 아직 방문하지 않았으므로 이를 처리.

image

  • [Step 3] 우선순위 큐에서 원소를 꺼냄. 2번 노드는 아직 방문하지 않았으므로 이를 처리.

image

  • [Step 4] 우선순위 큐에서 원소를 꺼냄. 5번 노드는 아직 방문하지 않았으므로 이를 처리.

image

  • [Step 5] 우선순위 큐에서 원소를 꺼냄. 3번 노드는 아직 방문하지 않았으므로 이를 처리.

image

  • [Step 6] 우선순위 큐에서 원소를 꺼냄. 3번 노드는 이미 방문했으므로 무시.

image

  • [Step 7] 우선순위 큐에서 원소를 꺼냄. 6번 노드는 아직 방문하지 않았으므로 이를 처리.

image

  • [Step 8] 우선순위 큐에서 원소를 꺼냄. 3번 노드는 이미 방문했으므로 무시.

image

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

n, m = map(int, sys.stdin.readline().split())

start = int(sys.stdin.readline())

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

visited = [False] * (n + 1)

distance = [INF] * (n + 1)

for _ in range(m):
    a, b, c = map(int, sys.stdin.readline().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 = 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])
  1. 시작 노드가 1이라면 1에서 1가는건 0이기 때문에 최단 경로를 0으로 설정해줘서 (0, 1)을 큐에 삽입
  2. distance라는 list는 최단 경로를 저장해주는 리스트로써 distance[1] = 0으로 설정
  3. q가 빌때까지 루프
    • 가장 거리가 가까운 노드 heappop()
    • 가장 거리가 가까운 노드의 거리가 distance 리스트에 저장되어 있는 거리보다 크다면 이미 distance list에 최단 거리가 저장된 것이기 때문에 무시
    • 그게 아니라면 해당 노드가 갈 수 있는 노드들 탐색
      • cost라는 변수를 줘서 최단 거리로 뽑힌 dist에 해당 노드가 갈 수 있는 노드까지의 거리를 더해준 것들을 검사
      • 만약 cost 변수에 저장된 값이 distance list에 저장된 값보다 작다면?
        • 작은 값으로 distance list 업데이트
        • 업데이트한 거리 값과 해당 노드를 push

풀이(다익스트라 우선순위 큐 사용)

  • 여기서 추가된 것은 특정 노드를 지나야만 한다이다.
  • 조심해야 할 것은 예를 들어 2, 3번 노드를 꼭 지나야 한다고 했으면 2번 노드를 거쳐서 3번 노드로 가는 경우와 3번 노드를 거쳐서 2번 노드로 가는 경우 2가지를 생각해야 한다.
  • 예를 들어보자면
  • 4번 노드까지 가야 하는데 2, 3번 노드를 거쳐야 한다?
  • 2번 노드까지 가는 최단 거리와 3번 노드까지 가는 최단 거리를 구한다.
  • 그 후, 2번 노드에서 4번 노드까지 가는 최단 거리와 3번 노드에서 4번 노드까지 가는 최단 거리를 구한다.
  • 그 후, 1 -> 2 가는 최단 거리와 2 -> 3 까지의 거리, 그리고 3 -> 4 까지 가는 최단 거리를 다 더한것과 1 -> 3, 3 -> 2, 2 -> 4 를 비교한다. 그 중 가장 작은 값이 정답이 된다.
  • 만약 그런 값이 없다면 -1을 출력한다.

주의

  • 방향성이 없는 그래프라 2 -> 3 으로 가는 간선의 거리만 입력을 받았다고 하더라도 3 -> 2 로 가는 간선의 거리도 같기 때문에 같은 값을 서로 넣어주어야 한다.
  • 2 -> 3 까지의 최단 경로와 3 -> 2 까지의 최단 경로는 다를 수 있다. 방향성이 없는 그래프라 둘 사이의 간선의 거리는 같지만, 최단 경로는 다른 노드를 통해서 가는 것이 더 빠를 수도 있다.

첫번째 오답코드(dfs 사용)

import sys

N, E = map(int, sys.stdin.readline().split())

graph = [[] for _ in range(N + 1)]
visit = [False] * (N + 1) 
dis_list = []

for i in range(E):
    a, b, c = map(int, sys.stdin.readline().split())
    graph[a].append([b, c])
    graph[b].append([a, c])

v1, v2 = map(int, sys.stdin.readline().split())

for i in range(N + 1):
    graph[i].sort()

def dfs(v, distance, sum_dis, v1, v2):
    sum_dis += distance
    for i in range(len(graph[v])):
        if visit[graph[v][i][0]] == True:
            continue
        else:
            visit[graph[v][i][0]] = True
            if graph[v][i][0] == N:
                if visit[v1] == True and visit[v2] == True:
                    dis_list.append(sum_dis + graph[v][i][1])
                visit[v] = False
                visit[N] = False
                return 
            else:
                dfs(graph[v][i][0], graph[v][i][1], sum_dis, v1, v2)
    if visit[1] == False:
        return
visit[1] = True
dfs(1, 0, 0, v1, v2)
dis_list.sort()
if len(dis_list) == 0:
    print(-1)
else: 
    print(dis_list[0])

두번째 정답코드(다익스트라 우선순위 큐 사용)

import sys
import heapq

INF = int(1e9)

N, E = map(int, sys.stdin.readline().split())

graph = [[] for i in range(N + 1)]

distance = [INF] * (N + 1)

for _ in range(E):
    a, b, c = map(int, sys.stdin.readline().split())
    graph[a].append((b, c))
    graph[b].append((a, c))

v1, v2 = map(int, sys.stdin.readline().split())

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 = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))
sum1 = 0
sum2 = 0
check2 = False
dijkstra(1)
sum1 += distance[v1]
sum2 += distance[v2]
distance = [INF] * (N + 1)
dijkstra(v1)
sum1 += distance[v2]
sum2 += distance[N]
distance = [INF] * (N + 1)
dijkstra(v2)
sum1 += distance[N]
sum2 += distance[v1]


if sum1 >= INF and sum2 >= INF:
    print("-1")
    exit()
else:
    if sum1 >= INF:
        print(sum2)
    elif sum2 >= INF:
        print(sum1)
    else:
        if sum1 > sum2:
            print(sum2)
        else:
            print(sum1)

고찰

  • dfs의 시간 복잡도는 O(2 * E * V) = O(E * V)이며 다익스트라의 시간 복잡도는 O(ElogV)이다.
  • 그래서 dfs로 문제를 풀었을 때는 시간초과가 뜨게 되며 다익스트라로 풀되 일반적인 다익스트라 풀이가 아닌 우선순위 큐를 이용하여야 시간초과가 뜨지 않게 된다.

image

댓글남기기

참고