날마다 새로운 코딩

1. 문제 : https://www.acmicpc.net/problem/2211 2211번: 네트워크 복구 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다 www.acmicpc.net 2. 풀이 : Dijkstra 3. 설명 문제의 조건은 아래와 같다. 1. 모든 컴퓨터를 최소 개수의 회선으로 복구한다. 2. 슈퍼컴퓨터가 다른 컴퓨터들과 통신하는데 걸리는 시간이 최소가 되어야 한다. 모든 컴퓨터를 최소의 회선으로 복구하려면 (컴퓨터 수 - 1) 만큼의 회선이 필요하다. 슈퍼컴퓨터로부터 모든 컴퓨터를 최소의 시간으로 연결하면서 경로를 갱신..

Algorithm/Dijkstra 2021. 7. 21. 20:22

1. 문제 : https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 2. 풀이 : 다익스트라 3. 설명 그림[1]에서 도착점인 5번 노드까지의 최단 경로는 다익스트라의 구현 방법에 따라 1->3->5 혹은 1->4->5 2가지의 최단 경로가 가능하다. 경로 추적 배열은 출발점인 1번 노드는 -1로 갱신하고, 각 노드의 최단 거리가 갱신되는 시점에 갱신한다. 최단 경로를 다 찾은 후, 도착점부터 출발점까지 경로를 역추적..

Algorithm/Dijkstra 2021. 7. 14. 21:45

1. 문제 : https://www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 2. 풀이 : 다익스트라 3. 설명 그림[1]과 같이 네트워크 시설이 존재할 때, 1번 컴퓨터를 해킹하면 그림[2]와 같다. 5번 컴퓨터를 제외한 총 4대의 컴퓨터가 감염이되며, 이때 마지막 컴퓨터까지 감염이 되는 시간은 5초이다. 4. 코드

Algorithm/Dijkstra 2021. 7. 14. 21:05

1. 문제 : https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 2. 풀이 : Dijkstra 3. 시간복잡도 : O(ElogV) 4. 설명 그림[1]의 그래프에서 시작점이 1번 노드 일 때, 각 노드까지의 최단거리를 구하는 방법은 다음과 같다. 시작점인 1번 노드를 우선순위큐에 삽입한다. 시작점에서 시작점까지의 최단거리는 0이다. 노드 1에서 최단 거리로 방문 할 수 있는 노드를 우선순위큐에 삽입하고, 최단 거리를 갱..

Algorithm/Dijkstra 2021. 7. 7. 22:22