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을 출발선이라고 하고 위의 설명과..

문제해결 1.최단거리를 저장할 최대힙을 만들어준다. 2.최대힙의 사이즈가 k보다 작으면 무조건 push 3.최대힙의 사이즈가 k이고 top의 값이 new_val보다 크면 pop후 new_val를 push 한다. 4.이런 식으로 다익스트라 알고리즘을 응용한다. 코드 (코드의 주석이 상세하게 적혀있어 보시면 이해가 바로 되고 도움되실거예요!) ide.goorm.io/shared_files/sksj0111_250e20fbfd92552322517b1b09da0ed61603463344960 1854(3).cpp - goorm 구름IDE에서 공유된 소스코드를 볼 수 있는 페이지입니다. ide.goorm.io:443

https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있�� www.acmicpc.net 문제해결 1. 다익스트라 알고리즘을 통해 목적지까지의 최단 거리를 구한다. 2.최단거리를 구하면서 최단거리의 이전노드들을 trace 벡터에 저장하면서 구한다. 3.trace의 있는 노드의 간선들을 재귀를 통해서 제거한다. 4.다시 한번 다익스트라 알고리즘을 돌려서 최단거리를 구한다. 5.코드에 주석 열심히 달았어요 보면은 이해 될 거예요. 코드 ide.goorm...