문제

1. 첫 번째 줄에 도시의 수 N이 주어짐 (1 ≤ N ≤ 1,000)
2. 두 번째 줄에 두 도시를 오가는 버스의 수 M이 주어짐 (1 ≤ M ≤ 100,000)
3. 세 번째 줄부터 M줄 만큼 도시간 이동비용이 주어짐
4. 마지막 줄에 출발할 도시와 도착하려는 도시가 주어짐
5. 출발 도시에서 도착 도시까지 이동 시 최소 비용을 계산하여 반환

---

접근방법 및 주의사항

정석대로 접근하기

1. 도시의 수를 바탕으로 2차원 배열을 생성하여 이것을 graph로 사용함
2. 버스의 수만큼 반복문을 돌며 graph를 채움
3. dijkstra algorithm을 이용하여 최소 비용을 계산함

주의사항

1. 도시의 index가 1부터 시작함
   • 배열에 넣을 때 index에 신경을 써야 함
2. 두 도시 사이에 비용이 여럿 존재할 수 있음 (multi graph)
   • 입력으로 받은 비용 중 최소 비용으로 설정
3. dijkstra algorithm의 최대 값을 넉넉히 설정해야 함
   • N과 M이 최대 값으로 사용되는 경우를 고려해야 함
   • limit.h의 INT_MAX로 처리할 수 있음

---

문제 풀이

graph 생성

1. 2차원 배열로 graph를 생성함
2. 입력받은 도시의 번호에서 1을 뺀 값을 index로 사용함
3. 마찬가지로 출발 도시와 시작 도시의 index도 입력받은 값에서 1을 빼야 함
4. graph를 생성하는 과정에서 이미 비용이 설정되어 있다면 기존값과 비교하여 최소값을 저장함

dijkstra algorithm

1. 각 도시에 대한 방문 비용 정보를 초기화 함
   • 모든 도시에 방문하는 비용을 무한대(INT_MAX)로 설정함
   • 모든 도시를 방문하지 않은 상태로 설정함
   • 시작 도시의 방문 비용만 0으로 설정함
2. 방문하지 않는 도시 중 방문 비용이 가장 낮은 도시(u)를 찾고, 방문한 것으로 설정함
3. 모든 방문하지 않은 도시(v)에 대하여, 아래 두 값 중 작은 값을 자신의 방문 비용으로 설정함
   • 시작 도시에서 v로 바로 가는 비용
   • 시작 도시에서 u를 거쳐 v로 가는 비용
4. 목적지에 방문하는 비용을 반환함

function dijkstra(N, src, dest, graph):
	for each vertex v in graph.vertices:
    	dist[v] ← INFINITY
    	set v to an unvisited vertex
	dist[source] ← 0
    
    while the unvisited vertices exist:
    	u is an unvisited vertex with min dist[u]
        set u to a visited vertex
        
    for each unvisited neighbor v of u:
    	alt ← dist[u] + graph.edge(u, v)
        if alt < dist[v]:
        	dist[v] ← alt
            
	return dist[dest]

방문 비용이 최소인 도시 찾기

• 정렬 알고리즘을 이용하여 빠르게 최소 값을 얻을 수 있다.
• 하지만 도시의 수가 1000개 이하이므로 단순히 반복문을 이용하여 찾아도 무방하다.