겜돌이의 개발일지

개요 다익스트라 알고리즘은 하나의 정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘이라면, 플로이드-와샬 알고리즘은 모든 정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘이다. 이차원 배열을 사용해 최소값을 계속 저장해두기 때문에, 다이나믹 프로그래밍 기법의 일부로도 볼 수 있다. 설명 A에서 B로 가는 최소 비용과 A에서 C를 거쳐 B로 가는 최소 비용을 비교한다. 다음과 같은 비용을 가지는 양방향 그래프가 있다고 가정하다. 초기값을 먼저 표시하면 다음 표와 같다. 1을 지날 때 다음 영역을 갱신 해줘야 한다. 4 -> 1-> 5 (반대도 같음)의 비용이 14이므로 INF에서 갱신해준다. 2를 지날 때 3 -> 2 -> 4 (반대도 같음)의 비용이 7로, 기존의 비용 8보다 더 저렴하..

문제 백준 11725 트리의 부모 찾기 C++ 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 1이 루트기 때문에, 1에서 DFS나 BFS를 실행하면 된다. 해당 노드에 처음 방문했을 때, 그 전 노드가 부모가 된다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 #include #include #inc..

문제 백준 1647 도시 분할 계획 C++ 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 풀이 최소 스패닝 트리를 이용한다. 1. 엣지들을 가중치에 대해 오름차순으로 정렬해주고 2. 최소 스패닝 트리를 만족하도록 가중치가 낮은 n - 2개의 엣지를 연결하면 두 그룹으로 나뉘게 된다. 3. 지금까지의 가중치의 합(ans)가 정답이 된다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 2..