이번에 해결한 알고리즘 문제는
Find the Hub이다
sssp (single-source shortest path)와
apsp (all-pair shortest path)를 이용해서
city들 중에서 hub city를 찾는 알고리즘 문제이다
문제에서 찾아야하는 hub city는
주어지는 distance threshold 이하의 거리로
가장 많은 도시들을 연결하는 city이다
이번 문제의 자세한 설명은 위와 같다
input으로는 총 3개가 들어오는데
도시의 개수인 n
double array 형식의 edges
그리고 distanceThreshold가 들어온다
위 예시의 경우 city1은 총 3개의 도시를 threshold보다 같거나 작은 거리로 연결하고
city2도 동일하게 3개의 도시를 threshole보다 같거나 작은 거리로 연결한다
이렇게 tie되는 상황이 발생했을 경우는
city number가 더 큰 것이 정답이 된다
따라서 위 예시의 정답은 2가 된다
input과 output 그리고 constraint다
위 알고리즘 문제를
Floyd-Warshall Algorithm과
Bellman-Ford Algorithm
2가지 방법으로 해결해보려고한다
Floyd-Warshall Algorithm 강의내용정리는
[computer science] all-pair shortest path(2) (Floyd-Warshall Algorithm, Johnson Algorithm)
이 게시글은서울대학교 데이터사이언스대학원조요한 교수님의데이터사이언스 응용을 위한 컴퓨팅 강의를학습을 위해 재구성하였습니다.이번 시간은 apsp의 두번째 강의 내용을 정리해보려고
think0905.tistory.com
Bellman-Ford Algorithm 강의내용정리는
[computer science] single-source shortest path(2), Bellman-Ford Algorithm(벨만포드 알고리즘)
이 게시글은서울대학교 데이터사이언스대학원조요한 교수님의데이터사이언스 응용을 위한 컴퓨팅 강의를학습을 위해 재구성하였습니다. 저번 시간에 다익스트라 알고리즘에 대해 배웠는데
think0905.tistory.com
여기에 ㅎㅎ..
Floyd-Warshall Algorithm
Floyd-Warshall Algorithm을 이용해서
이 문제를 해결하기 위해서 큰 단계를 세워봤다
1. shortest path담을 double-array 변수 선언 + 무한대로 초기화
2. source랑 destination 같은 건 0으로 update
3. input으로 받은 edges로 double-array update
4. Floyd-Warshall Algorithm으로 shortest path업데이트
5. 각 vertex마다 distanceThreshold보다 작은경로 count
6. count가 가장 큰 것 + city number가 가장 큰 것 return
각 단계별 구현을 코드로 살펴보자
vector<vector<int> > graph(n, vector<int>(n, 1000001));
// i랑 j같을 때 0으로 초기화하기
for (int i=0; i<=n-1; i++) {
for (int j=0; j<=n-1; j++) {
if (i == j) { graph[i][j] = 0; }
}
}
// undirected라서 양방으로 weight 채우기
for (const auto& edge : edges) {
graph[edge[0]][edge[1]] = edge[2];
graph[edge[1]][edge[0]] = edge[2];
}
우선 가장 처음에 shortest path를 담을
double-array형식의 변수를 vector 형식으로 선언해준다
그리고 초기화를 무한대로 해주어야하는데
constraint를 보면 weight의 최대값은 10^4이고
n은 최대 100개까지 있을 수 있으므로
모든 weight들의 합은 최대 10^4 * 100이 될 수 밖에없다
따라서 10^4 * 100보다 1큰 값으로 초기화를 해주었다
그다음은 source와 destination이 같은건
0으로 update를 시켜줬다
그다음 input으로 받아오는 edges들을 loop를 돌면서
해당 weight만큼을 update해줬다
여기서 중요한건 도시와 도시간의 경로는
양방향(undirected)이기 때문에
양방향으로 weight를 update해줘야한다
(이걸 생각못해서 처음에 틀렸..)
// 그 다음에 min값 update
// Floyd-Warshall Algorithm
for (int k=0; k<=n-1; k++) {
for (int i=0; i<=n-1; i++) {
for (int j=0; j<=n-1; j++) {
graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
}
}
}
이제 Floyd-Warshall Algorithm을 수행해준다
이 알고리즘의 핵심은 중간 vertex k를 지나가는
경로가 있는지 없는지이다
따라서 k를 지나가는 경로가 있을때의 거리와
k를 지나가지 않는 거리 중에서
최솟값을 update해준다
// 각 vertex별로 distanceThreshold보다 작은 path count
vector<int> resultVec(n, 0);
for (int i = 0; i <= n-1; i++) {
int cnt = 0;
for (int j = 0; j<=n-1; j++) {
if (graph[i][j] <= distanceThreshold && i != j) {
cnt++;
}
}
resultVec[i] = cnt;
}
// 최댓값 찾기
// tie값이 생길 때 더 큰 city를 return하니깐 큰 수부터 역순으로 loop
int cityResult = -1;
int countResult = 0;
for (int i =n-1; i>=0; i--) {
if (countResult < resultVec[i]) {
cityResult = i;
countResult = resultVec[i];
} else if (countResult == resultVec[i]) {
if (cityResult < i) {
cityResult = i;
countResult = resultVec[i];
}
}
}
return cityResult;
}
이제 shortest path를 모두 구했기때문에
각 city별로 distanceThreshold를 넘기지않고
도달하는 city의 개수를 구해준다
resultVec이라는 vec을 만들어서
각 city의 index마다 threshold 이하인 경로의 개수를
찾아서 계산해준다
이제 위에서 만들어준 resultVec을 이용해서
연결된 threshold 이하 도시가 가장 많은 도시를 찾아준다
tie 상황이 생길 때는 두 도시 중 더 큰 도시를 선택해야하므로
for문은 역순으로 돌아주는게 더 효율적이라고 한다
따라서 가장 개수가 많은 도시의 값을
결과로 return해주면 해결!
Floyd-Warshall Algorithm의 전체 코드는 아래와 같다
int floydWarshall (int n, std::vector<std::vector<int>>& edges, int distanceThreshold) {
vector<vector<int> > graph(n, vector<int>(n, 1000001));
// i랑 j같을 때 0으로 초기화하기
for (int i=0; i<=n-1; i++) {
for (int j=0; j<=n-1; j++) {
if (i == j) { graph[i][j] = 0; }
}
}
// undirected라서 양방으로 weight 채우기
for (const auto& edge : edges) {
graph[edge[0]][edge[1]] = edge[2];
graph[edge[1]][edge[0]] = edge[2];
}
// 그 다음에 min값 update
// Floyd-Warshall Algorithm
for (int k=0; k<=n-1; k++) {
for (int i=0; i<=n-1; i++) {
for (int j=0; j<=n-1; j++) {
graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
}
}
}
// 각 vertex별로 distanceThreshold보다 작은 path count
vector<int> resultVec(n, 0);
for (int i = 0; i <= n-1; i++) {
int cnt = 0;
for (int j = 0; j<=n-1; j++) {
if (graph[i][j] <= distanceThreshold && i != j) {
cnt++;
}
}
resultVec[i] = cnt;
}
// 최댓값 찾기
// tie값이 생길 때 더 큰 city를 return하니깐 큰 수부터 역순으로 loop
int cityResult = -1;
int countResult = 0;
for (int i =n-1; i>=0; i--) {
if (countResult < resultVec[i]) {
cityResult = i;
countResult = resultVec[i];
} else if (countResult == resultVec[i]) {
if (cityResult < i) {
cityResult = i;
countResult = resultVec[i];
}
}
}
return cityResult;
}
Bellman-Ford Algorithm
이제 동일한 문제를 Bellman-Ford Algorithm으로 해결해보자
Bellman-Ford Algorithm은 single source에 대해서
shortest path를 구하는 알고리즘이기때문에
위의 문제처럼 모든 Vertex에 대해 다 shortest path를 구해야하는 경우는
Bellman-Ford Algorithm을 모든 vertex에 대해서
다 돌려야한다
따라서 Bellman-Ford Algorithm을 이용해서
위 문제를 해결하는 큰 단계는 다음과 같이 세웠다
1. 모든 vertex에 대한 shortest path결과를 저장할 matrix를
double-array 형태로 선언, 무한대로 초기화
2. 모든 vertex에 대해서 Bellman-Ford Algorithm 실행
-> for i from 0 to n-1
-> for p from 0 to n-2
-> for edges
위와같은 순서로 for loops를 돌린다
3. 각 vertex마다 distanceThreshold보다 작은경로 count
4. count가 가장 큰 것 + city number가 가장 큰 것 return
이제 코드로 자세하게 구현해보도록 하자
vector<vector<int> > bf(n, vector<int>(n, 100001));
// 모든 vertex를 source로
for (int i=0; i<=n-1; i++) {
bf[i][i] = 0;
// 전체 vertex-1번만큼 pass돌기
for (int p=0; p<=n-2; p++) {
// edges 대해서 loop
for (const auto& edge : edges) {
// bellman-ford algorithm
// 양방향(undirected)라서 2번 update
bf[i][edge[1]] = min(bf[i][edge[1]], bf[i][edge[0]] + edge[2]);
bf[i][edge[0]] = min(bf[i][edge[0]], bf[i][edge[1]] + edge[2]);
}
}
}
우선 가장 위에 shortest path를 저장할 double array를
vector 타입으로 선언해준다
위와 동일하게 초기화할 무한대 값은
constraints에 따라 weight의 합이 가질 수 있는 최댓값에
1을 더한 값으로 설정해줬다
그다음 본격적으로 bellman-ford 알고리즘을 수행해주자
원래 정석대로라면 bellman-ford 알고리즘은
한 개의 source vertex를 대상으로 수행하므로
각 vertex까지의 거리를 구하는 array를 만들어 수행한다
하지만 이 경우는 어차피 모든 vertex에 대해 수행해야하므로
Floyd-Warshall 알고리즘과 동일하게
모든 Vertex에 대한 matrix bf를 만들어줬다
그렇게되면
bf[0]는 결국 vertex 0에서 모든 vertex까지 최단경로를 담은 vector가되고
bf[1]은 위와 동일하지만 vertex1이 source가 되고
bf[2]도 vertex2가 source가 되는 것이다
따라서 for문에서 가장 먼저 이 row만큼을 돌려줬다
그런 다음 bellman-ford에서는 가장 처음에
source랑 destination이 같은 경우는 0으로 update를 해줘야해서
해당 부분을 수행해주었다
그런 다음 bellman-ford algorithm의 핵심인
pass만큼 for문을 돌려주는데
pass의 횟수는 전체 vertex 개수의 -1개이므로
n-2만큼 돌려준다
bellman-ford 알고리즘은 모든 edges들에 대해서
비교해서 shortest path를 찾아가는 알고리즘이다
모든 edge(u, v)에 대해서
v의 현재 shortest path값이
u의 현재 shortest path값에서 weight를 더한 것보다 작으면
새로 업데이트를 시켜주는 방식이다
따라서 edges에 대해서 for문을 돌면서
위 과정을 그대로 수행해준다
참고로 city간의 거리는 양방향이기때문에
엣지의 순서를 바꿔서 총 두번을 update해준다
// 각 vertex별로 distanceThreshold보다 작은 path count
vector<int> resultVec(n, 0);
for (int i = 0; i <= n-1; i++) {
int cnt = 0;
for (int j = 0; j<=n-1; j++) {
if (bf[i][j] <= distanceThreshold && i != j) {
cnt++;
}
}
resultVec[i] = cnt;
}
// 최댓값 찾기
// tie값이 생길 때 더 큰 city를 return하니깐 큰 수부터 역순으로 loop
int cityResult = -1;
int countResult = 0;
for (int i =n-1; i>=0; i--) {
if (countResult < resultVec[i]) {
cityResult = i;
countResult = resultVec[i];
} else if (countResult == resultVec[i]) {
if (cityResult < i) {
cityResult = i;
countResult = resultVec[i];
}
}
}
return cityResult;
}
이후의 과정은 Floyd-Warshall Algorithm에서 한 것과 동일하므로
따로 설명하지는 않겠다
아무튼 이렇게 cityResult를 Return해주면
Bellman-Ford algorithm을 이용해서
위 알고리즘 문제의 답을 내게 된다
Bellman-Ford 알고리즘의 전체 코드는 다음과 같다
int bellmanFord(int n, std::vector<std::vector<int>>& edges, int distanceThreshold) {
// bellman-ford algorithm
vector<vector<int> > bf(n, vector<int>(n, 100001));
// 모든 vertex를 source로
for (int i=0; i<=n-1; i++) {
bf[i][i] = 0;
// 전체 vertex-1번만큼 pass돌기
for (int p=0; p<=n-2; p++) {
// edges 대해서 loop
for (const auto& edge : edges) {
bf[i][edge[1]] = min(bf[i][edge[1]], bf[i][edge[0]] + edge[2]);
bf[i][edge[0]] = min(bf[i][edge[0]], bf[i][edge[1]] + edge[2]);
}
}
}
// 각 vertex별로 distanceThreshold보다 작은 path count
vector<int> resultVec(n, 0);
for (int i = 0; i <= n-1; i++) {
int cnt = 0;
for (int j = 0; j<=n-1; j++) {
if (bf[i][j] <= distanceThreshold && i != j) {
cnt++;
}
}
resultVec[i] = cnt;
}
// 최댓값 찾기
// tie값이 생길 때 더 큰 city를 return하니깐 큰 수부터 역순으로 loop
int cityResult = -1;
int countResult = 0;
for (int i =n-1; i>=0; i--) {
if (countResult < resultVec[i]) {
cityResult = i;
countResult = resultVec[i];
} else if (countResult == resultVec[i]) {
if (cityResult < i) {
cityResult = i;
countResult = resultVec[i];
}
}
}
return cityResult;
}
time complexity
그럼 Floyd-Warshall과 Bellman-Ford로 수행했을 때의
time complexity를 한 번 살펴보자
Floyd-Warshall은 vertex의 개수 n에 대해서 총 3번의 loop를
중첩하며 도므로 O(n^)이다
Bellman-Ford는 모든 vertex n개에 대해서
n-1번의 pass만큼 edge개수 E만큼 중첩해서 loop를 도므로
O(n * (n - 1) * E)가 나오는데
Big-O 표기법에서는 n-1은 n으로 bound가 되면서
O(n^2 * E)만큼이 된다
보통 그래프에서 vertex의 개수가 n이라고 한다면
가질 수 있는 edge의 개수는 최대 n^2개이다
만약 어떤 그래프의 edge의 개수가
n^2에 가까워질수록(그래프가 밀집할수록)
Bellman-ford의 시간복잡도는 Floyd-Warshall에 동일해진다
하지만 edge의 개수가 적은 희소 그래프일수록
Bellman-Ford 알고리즘이 더 좋은 성능을 보인다
결과 확인
위 Floyd-Warshall과 Bellman-Ford 함수를
Solution이라는 class에 넣어서
여러 가지 case들에 대해서 test를 해보았다
int main() {
Solution solution;
int n1 = 4;
std::vector<std::vector<int>> edges1 = {{0, 1, 3}, {1, 2, 1}, {1, 3, 4}, {2, 3, 1}};
int distanceThreshold1 = 4;
std::cout << "Test Case 1 (Floyd Warshall) Output: " << solution.floydWarshall(n1, edges1, distanceThreshold1) << std::endl; // Expected output: 2
std::cout << "Test Case 1 (Bellman Ford) Output: " << solution.bellmanFord(n1, edges1, distanceThreshold1) << std::endl; // Expected output: 2
int n2 = 5;
std::vector<std::vector<int>> edges2 = {{0, 1, 2}, {0, 4, 8}, {1, 2, 3}, {1, 4, 2}, {2, 3, 1}, {3, 4, 1}};
int distanceThreshold2 = 2;
std::cout << "Test Case 2 (Floyd Warshall) Output: " << solution.floydWarshall(n2, edges2, distanceThreshold2) << std::endl; // Expected output: 4
std::cout << "Test Case 2 (Bellman Ford) Output: " << solution.bellmanFord(n2, edges2, distanceThreshold2) << std::endl; // Expected output: 4
int n3 = 3;
std::vector<std::vector<int>> edges3 = {{0, 1, 1}, {1, 2, 1}, {0, 2, 2}};
int distanceThreshold3 = 2;
std::cout << "Test Case 3 (Floyd Warshall) Output: " << solution.floydWarshall(n3, edges3, distanceThreshold3) << std::endl; // Expected output: 2
std::cout << "Test Case 3 (Bellman Ford) Output: " << solution.bellmanFord(n3, edges3, distanceThreshold3) << std::endl; // Expected output: 2
int n4 = 4;
std::vector<std::vector<int>> edges4 = {{0, 1, 3}, {2, 3, 1}};
int distanceThreshold4 = 2;
std::cout << "Test Case 4 (Floyd Warshall) Output: " << solution.floydWarshall(n4, edges4, distanceThreshold4) << std::endl; // Expected output: 3
std::cout << "Test Case 4 (Bellman Ford) Output: " << solution.bellmanFord(n4, edges4, distanceThreshold4) << std::endl; // Expected output: 3
int n5 = 1;
std::vector<std::vector<int>> edges5 = {};
int distanceThreshold5 = 0;
std::cout << "Test Case 5 (Floyd Warshall) Output: " << solution.floydWarshall(n5, edges5, distanceThreshold5) << std::endl; // Expected output: 0
std::cout << "Test Case 5 (Bellman Ford) Output: " << solution.bellmanFord(n5, edges5, distanceThreshold5) << std::endl; // Expected output: 0
int n6 = 100;
std::vector<std::vector<int>> edges6 = {
{0, 1, 10000}, {0, 2, 5000}, {1, 2, 4000}, {2, 3, 7000}, {3, 4, 2000},
{4, 5, 8000}, {5, 6, 6000}, {6, 7, 9000}, {7, 8, 3000}, {8, 9, 10000}
};
int distanceThreshold6 = 20000;
std::cout << "Test Case 6 (Floyd Warshall) Output: " << solution.floydWarshall(n6, edges6, distanceThreshold6) << std::endl; // Expected output: 5
std::cout << "Test Case 6 (Bellman Ford) Output: " << solution.bellmanFord(n6, edges6, distanceThreshold6) << std::endl; // Expected output: 5
int n7 = 50;
std::vector<std::vector<int>> edges7 = {
{0, 1, 300}, {1, 2, 200}, {2, 3, 400}, {3, 4, 500}, {4, 5, 300},
{5, 6, 600}, {6, 7, 700}, {7, 8, 100}, {8, 9, 200}, {9, 10, 500},
{10, 11, 400}, {11, 12, 300}, {12, 13, 600}, {13, 14, 700}, {14, 15, 200}
};
int distanceThreshold7 = 1500;
std::cout << "Test Case 7 (Floyd Warshall) Output: " << solution.floydWarshall(n7, edges7, distanceThreshold7) << std::endl; // Expected output: 12
std::cout << "Test Case 7 (Bellman Ford) Output: " << solution.bellmanFord(n7, edges7, distanceThreshold7) << std::endl; // Expected output: 12
return 0;
}
위 main함수를 실행하면
이렇게 아름다운 결과가 나오는 것을 확인할 수 있다
test case에 negative-weight가 없는 것 같은데
다익스트라로 한 번 연습해보는 것도 좋을 것 같다
'기술 > 알고리즘' 카테고리의 다른 글
| [c++] Min Cost to Connect All Points 문제 Prim's Algorithm으로 해결하기 (1) | 2024.12.13 |
|---|---|
| [c++] MaxHeapify, BuildMaxHeap으로 HeapSort 구현하기 (0) | 2024.12.13 |
| [c++] Height Order 문제 해결하기 (Floyd-Warshall's Algorithm, Topological Sort) (2) | 2024.12.05 |
| [c++] tree structure를 base로 한 max heap 구현하기 (1) | 2024.12.02 |
| [c++] tree가 valid한 Red-Black Tree 확인하는 알고리즘 (0) | 2024.12.02 |