겜돌이의 개발일지

문제 백준 11404 플로이드 C++ 풀이 전형적인 플로이드-와샬 알고리즘 문제이다. 3중 포문을 통해 모든 정점에서부터 모든 정점까지의 최소 거리를 구한다. 소스 코드 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 61 62 63 64 65 66 67 68 69 #include #include using namespace std; const int INF = 987654321; int n, m; int dist[101][101]; int main(..

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

문제 백준 2660 회장뽑기 풀이 각 정점마다 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 61 62 63 64 65 66 67 68 69 70 71 72 73 #include #include #include #include #include using namespace std; vector v[51]; bool visited[51]; int N; i..