4Legs_Archives

문제 링크 : www.acmicpc.net/problem/13141 13141번: Ignition 첫 번째 줄에는 그래프의 정점의 수 N과 간선의 수 M이 주어진다. (2 ≤ N ≤ 200, N-1 ≤ M ≤ 20,000) 두 번째 줄부터 M개의 줄에는 각 간선의 시작점 S, 끝점 E, 길이 L이 주어진다. (1 ≤ L ≤ 100) 시작점 www.acmicpc.net 간선들은 그 간선의 양 끝 노드에 불이 옮겨진 순간부터 타는 시간이 절반으로 줄어들게 된다. 쉽게 설명하자면 다음 그림과 같다. 정점 A에 불이 먼저 붙은 상황이다. 이 때, A와 B를 잇는 간선은 A쪽에서 먼저 타게 된다. B쪽에는 아직 불이 도착하지 않았기 때문이다. 이제 정점 B에도 불이 붙었다. 이제는 간선의 남은 길이가 양쪽에서 타..

문제 링크 : www.acmicpc.net/problem/1602 1602번: 도망자 원숭이 첫 번째 줄에는 도시의 개수 N (2 ≦ N ≦ 500) 과 도로의 개수 M (0 ≦ M ≦ 10,000), 그리고 질문의 개수 Q (0 ≦ Q ≦ 40,000) 가 주어진다. 그 다음 줄에, N개의 정수로 각 도시에서 멍멍이가 원숭이를 괴 www.acmicpc.net 문제에서 쿼리 형식으로 출발, 도착 노드에 대한 최소 시간을 묻고 있으므로, 모든 노드에 대해 다른 모든 노드까지의 최단경로를 구하는 플로이드-와샬 알고리즘이 적절할 것이다. 다만 도시 별 괴롭힘 시간이라는 별도의 가중치가 존재하는데, 멍멍이는 원숭이가 지나는 경로 중 가장 괴롭힘 시간이 긴 도시에서 괴롭히게 된다. 다만, 플로이드-와샬 알고리즘을..

문제 링크 : www.acmicpc.net/problem/2610 2610번: 회의준비 첫째 중에 회의에 참석하는 사람의 수 N이 주어진다. 참석자들은 1부터 N까지의 자연수로 표현되며 회의에 참석하는 인원은 100 이하이다. 둘째 줄에는 서로 알고 있는 관계의 수 M이 주어진다. 이 www.acmicpc.net 문제를 그래프의 관점에서 이해하면 다음과 같다. ① 서로 연결된 사람은 같은 위원회에 참석한다 = 그래프에서 연결된 노드들은 같은 위원회(그룹)로 취급한다. ② 효율적인 회의 진행을 위해 위원회의 수는 최대가 되어야 한다. = 그래프의 모든 정점에 대해 그룹화한다. 즉 그래프의 모든 정점에 대해 연결된 노드끼리 그룹(위원회)으로 묶은 후, 그룹의 대표 노드에 대해 다른 모든 노드에 대한 전파 시..

문제 링크 : www.acmicpc.net/problem/10159 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net 플로이드-와샬 문제라는 것을 캐치하는 것이 문제 해결의 80%는 되는 것 같은 문제이다. 각 물건들의 무게 관계를 그래프의 형태로 이해하고, 문제에서 요구하는 것이 그래프의 각 노드에서 도달할 수 없는 노드들의 갯수이므로 모든 노드에서 다른 모든 노드로의 최단거리를 구하는 플로이드-와샬 알고리즘이 적절함을 캐치해야 한다. 플로이드-와샬 알고리즘(Floyd-Warshall ..

[최단거리 알고리즘] 다익스트라 알고리즘 (Dijkstra Algorithm) 벨만-포드 알고리즘 (Bellman-Ford Algorithm) [서론] 최단거리 알고리즘의 마지막, 플로이드-와샬 알고리즘(이하 플로이드 알고리즘)이다. 플로이드 알고리즘은 그래프에서 모든 정점에서 다른 모든 정점까지의 최단거리를 구하는 알고리즘이다. 그래서 이전까지의 최단거리 알고리즘과는 다르게 dist배열이 처음부터 2차원 배열 형태이다. 벨만-포드 알고리즘과 마찬가지로 음의 가중치가 존재하는 그래프에서도 사용 가능하며, 음의 사이클이 존재하는 경우 최단거리를 구할 수 없다. [동작 원리] 플로이드 알고리즘은 출발 노드, 도착 노드 그리고 중간 노드를 통해 DP와 유사하게 동작한다. 편의상 이들을 From, To, Mid..