KPU CE

문제 https://www.acmicpc.net/problem/2211 2211번: 네트워크 복구 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다 www.acmicpc.net 문제 해결 1. 인접 리스트로 데이터들을 받는다. 2. 다익스트라 알고리즘을 실행한다. 3. 다익스트라 알고리즘에서 만약 new_val이 더 작으면 trace배열의 trace[next_node] = node 로 해준다. 4. 이렇게 해주면 해당노드의 최단거리의 부모를 알 수 있다. 5. trace배열을 각 노드들 별로 출력해준다. 코드 1234567891011121..

다익스트라 알고리즘은 출발 노드로부터 각 노드들의 최단거리를 구하는 알고리즘이다. 다익스트라 알고리즘을 이해하기 위해서는 일단 인접 리스트에 대해서 먼저 공부해야 이해할 수 있으므로 인접 리스트에 대해서 공부해오자. 예를 들어서 설명해보겠다. 위와 같은 가중치가 있는 그래프가 있다. 여기서 출발지가 1이라고 했을 때 각 노드들로 가는 최단경로를 구하는 것이 다익스트라 알고리즘이다. 1 2 3 4 5 infy infy infy infy infy 위와 같이 최단거리를 저장해두는 배열 dist를 생성한다. 초기값은 무한으로 해둔다. 다익스트라 알고리즘은 다음 노드의 dist 값과 현재노드의 dist값+가중치를 비교하여 더 작은 값이 다음 노드의 dist가 되는 알고리즘이다. 1을 출발선이라고 하고 위의 설명과..