<PART 2>최단 경로 알고리즘 예제

<2> 미래도시

방문 판매원 A는 많은 회사가 모여 있는 공중 미래 도시에 있습니다. 공중 미래 도시에는 1번부터 N번까지의 회사가 있는데 특정 회사 끼리는 서로 도로를 통해 연결되어 있습니다.
방문 판매원 A는 현재 1번 회사에 위치해 있으며, X번 회사에 방문해 물건을 판매하고자 합니다.

- 특정 회사에 도착하는 방법은 회사끼리 연결되어 있는 도로를 이용해야만 함
- 연결된 2개의 회사는 양방향 이동가능
- 특정 회사와 다른 회사가 도로로 연결되어 있다면, 정확히 1만큼의 시간으로 이동가능

또한, 방문 판매원 A는 기대하던 소개팅에도 참석하고자 합니다. 소개팅의 상대는 K번 회사에 존재합니다.  따라서 방문판매원 A는 1번 회사에서 출발하여 K번 회사를 방문한 뒤에 X번 회사로 가는 것이 목표입니다. 이때 가능한 한 빠르게 이동하고자 합니다. 방문 판매원이 회사 사이를 이동하게 되는 최소 시간을 계산하는 프로그램을 작성하십시오. 소개팅의 상대방과 커피를 마시는 시간 등은 고려하지 않는다고 가정합니다.

예를 들어 N=5, X=4, K=5이고 회사 간 도로가 7개면서 각 도로가 다음 과 같이 연결되어 있을 때를 가정할 수 있습니다.
(1번,2번), (1번,3번), (1번,4번), (2번,4번), (3번,4번), (3번,5번), (4번,5번)
이때 방문 판매원 A가 최종적으로 4번 회사에 가는 경로를 (1번 - 3번 - 5번 - 4번)으로 설정하면, 소개팅에도 참석할 수 있으면서 총 3만큼의 시간으로 이동할 수 있습니다. 따라서 이 경우 최소 이동 시간은 3입니다.

입력 조건)
- 첫째 줄에 회사의 개수 N과 경로의 갯수 M이 공백으로 구분되어 차례대로 주어집니다. (1<=N,M<=100)
- 둘째 줄부터 M+1번째 줄에는 연결된 두 회사의 번호가 공백으로 구분되어 주어집니다.
- M+2번째 줄에는 X+K가 공백으로 구분되어 차례대로 주어집니다.(1<=K<=100)

출력 조건)
- 첫째 줄에 방문 판매원 A가 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

#플루이드 워셜 알고리즘 사용
INF = int(1e9)
 
#노드의 개수 및 간선의 개수를 입력받기
n,m = map(int,input().split())
 
#2차원 무한으로 채우기, (0~n까지 2차원 그래프 만들기)
graph = [[INF] * (n+1) for _ in range(n+1)]
 
#자기 자신에게 가는 비용은 초기화
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이라고 설정, 반대도 마찬가지 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)

풀이: 전형적인 플로이드 워셜 알고리즘 문제입니다. N의 범위가 100이하로 매우 한정적이기 때문에 구현이 간단한 플로이드 워셜 알고리즘을 이용하는 것이 유리합니다. 이 문제의 핵심 아이디어는 1번 노드에서 K를 거쳐 X로 가는 최단거리는 [1][K] + [K][X]라는 점입니다. 최단 거리느 문제는 그림으로 먼저 그려보는 것도 좋은 방법입니다.
코드 상으로는 플로이드 워셜 알고리즘대로
1. 먼저 무한의 수를 정의합니다.
2. 노드의 개수, 간선의 개수를 입력 받은 후 노드의 개수N만큼 무한으로 채운 2차원리스트로 그래프를 만듭니다.
3. 자기 자신에게 가는 비용은 0으로 초기화합니다.
4. 각 간선에 대한 정보를 제공 받아 그 값들로 설정해줍니다.
5. 여기서 점화식을 사용합니다. 플로이드 워셜 알고리즘이므로 3중 for문을 사용하여 거쳐가는 경우와 원래 값 중 최솟값으로 값을 다시 설정해 줍니다.
6. 수행된 결과를 출력합니다. 전부 다 출력해야 할 때는 2중 for문을 사용하여 전부 보여주지만 특정 값을 알기 위해서는 한개의 변수인 distance를 선언하여 값을 무한일때와 아닐 떄를 비교하여 값을 출력합니다.

배운 점: 플루이드 워셜 알고리즘을 처음 접했을 때, 개념은 이해가 갔지만 코드를 구현하는 방법에 대해서는 막막했다. 하지만 문제를 보고 알고리즘을 다시보니깐 거쳐서 가는 경우를 점화식인 다이나믹 프로그래밍 기법이 생각났다. 핵심적인 부분은 크게 다름이 없고 그 전의 코드도 거의 다이나믹 프로그래밍과 비슷한 방식이였다. 이래서 다익스트라는 그리디, 플루이드 워셜은 다이나믹 프로그래밍이라고 하는 구나 라는 것을 깨닫게 되었다.

<3> 전보
어떤 나라에는 N개의 도시가 있습니다. 도시 X에서 도시 Y로의 통로가 설치되어 있는 경우에만 전보를 보낼 수 있습니다. Y에서 X로 향하는 통로가 없다면 Y는 X에게 전보를 보낼 수 없습니다. 또한, 전보를 보낼 때는 일정시간이 소요됩니다.

어느날 C라는 도시에서 위급상황이 발생했습니다. 그래서 최대한 많은 도시로 전보를 보내고자 합니다. 전보는 도시 C에서 출발하여 각 도시 사이에 설치된 통로를 거쳐, 최대한 많이 퍼져나갈 것입니다. 각 도시의 번호와 통로가 설치되어 있는 정보가 주어졌을 때, 도시 C에서 보낸 전보를 받게 되는 도시의 갯수는 총 몇개인지, 도시들이 모두 메시지를 받는 데 까지 걸리는 시간은 얼마인지 계산하는 프로그램을 작성하세요.

입력 조건)
- 첫째 줄에는 도시의 개수 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<=Z<=1000)

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

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

출력 예시)
2 4

import heapq
 
INF = int(1e9) #무한의 의미하는 값, 10억
 
#노드의 개수, 간선의 개수를 입력받기
n,m,start = map(int,input().split())
#각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기
graph = [[] for i in range(n+1)]
#최단 거리 테이블을 모두 무한으로 초기화, 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 = []
    #시작 노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입
    heapq.heappush(q,(0,start))
    distance[start] = 0
    while q: #큐가 빌때까지 실행
        #가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
        dist, now = heapq.heappop(q)
        if distance < now:
            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]))
 
#다익스트라 알고리즘을 수행
dijkstar(start)
 
#도달할 수 있는 노드의 개수
count =0
#도달할 수 있는 노드 중에서, 가장 멀리 있는 노드와의 최단 거리
max_distance = 0
for d in distance:
    if d!= INF:
        count += 1
        max_distance = max(max_distance,d)
#시작 노드는 제외해야 아므로 count-1을 출력
print(count-1, max_distance)

풀이: 다익스트라 알고리즘이랑 완전히 똑같습니다. 한 도시에서 다른 도시까지의 최단 거리문제로 치환할 수 있으므로 다익스트라 알고리즘을 이용해서 풀 수 있습니다. 또한 N, M의 범위가 충분히 크기 때문에, 우선순위 큐를 이용하여 다익스트라 알고리즘을 작성해야 합니다. 이 문제를 이해하기 보다는 다익스트라 알고리즘을 이해해야 합니다.

배운 점: 다익스트라 알고리즘을 처음 공부할 때 진짜 무슨 말인지 1개도 이해가 가질 않았다. 두번 째로 다시보니깐 무슨 말인지 알겠다.
1. 1차원 리스트로 빈 graph를 만든다. (우선순위 큐를 사용할 것이므로)
2. 무한을 담은 1차원 리스트를 만든다.
3. 모든 간선 정보를 graph에 추가시킨다. 1차원 리스트이므로 append를 사용하고 튜플 형태로 저장한다.
4. 다익스트라 함수 생성
5. 빈 q 리스트를 만든 다음, heapq.heappush(q,(0,start))를 이용해 큐에 넣는다. 이때 시작 노드는 최단 경로가 0이므로 distance[start] = 0으로 해준다.
6. 큐이므로 큐가 빌 때까지 실행시킨다.
7. 가장 최단 거리가 짧은 노드에 대한 정보부터 실행해야 한다. 그러므로 튜플 형태로 저장해놓은 q를 꺼낼 때,  heappush튜플형태로 넣어놓은 (거리, 위치)를 dist, now로 저장해준다.
8. 이때 거리가 지금의 distance값보다 크다면 실행시킬 필요가 없으므로 continue하여 다시 while문 처음으로 돌아간다. (간선 정보를 받았던 게 쓰이는 게 아니라 순수 최단 거리만 계산해서 비교함)
9. 그게 아니라면 현재 위치에 연결된 간선정보 받았던 모든 노드들을 확인하여 cost를 계산한다.
10. 이때 계산한 cost가 현재 노드를 거쳐서 간선 정보로 받아서 다른 노드로 이동하는 거리가 지금 distance 저장되있는 것보다 낮다면 cost로 distance를 갱신하고 heap에 (해당 노드로의 총 비용, 해당노드)를 추가 시킨다.
11. 다익스트라 함수를 실행한다.
12 . 필요로 하는 출력 조건에 맞게 distance를 설정에 맞게 출력시킨다.