이 문제를 보고 BFS나 DFS로 풀려고 했으나
더 좋은 방법을 찾아서 풀었다.
그 방법은 플로이드 와샬 알고리즘인데 2차원 배열에서 한 정점에서 다른 모든 정점들을 방문 할 때 최소값으로 방문하도록 하는 알고리즘이다
여기선 한칸을 이동할때 비용이 같으므로 1로 통일 하였다.
다른 문제에서 한칸을 이동할때 비용이 다르면 1이 아니라 다른 값을 넣어 해야 할 것이다.
#include<iostream>
#include<algorithm>
int INF = 96748532;
const int MAX = 101;
using namespace std;
int n, m;
int gp[MAX][MAX];
void func() {
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j)
continue;
else if(gp[i][k]&&gp[k][j]){
if (gp[i][j] == 0) {
gp[i][j] = gp[i][k] + gp[k][j];
}
else {
gp[i][j] = min(gp[i][j], gp[i][k] + gp[k][j]);
}
}
}
}
}
}
int main() {
cin >> n >> m;
while (m--) {
int a, b;
cin >> a >> b;
gp[a][b] = gp[b][a] = 1; //한 정점에서 다른 정점으로 이동할 때 cost가 같으므로
}
func();
int idx;
int result = INF;
for (int i = 1; i <=n; i++) {
int sum = 0;
for (int j = 1; j <= n; j++) {
sum+=gp[i][j]; // 한 정점에서 다른 모든 정점들로 이동할 때 드는 cost 총 합
}
if (result > sum) {
result = sum;
idx = i;
}
}
cout << idx << "\n"; //정점의 index 출력
}
'문제풀이 > 백준' 카테고리의 다른 글
[C++] 백준 1931 문제풀이 (0) | 2021.02.16 |
---|---|
[C++] 백준 1927번 문제풀이 (0) | 2021.02.15 |
[C++] 백준 1764번 문제풀이 (0) | 2021.02.11 |
[C++] 백준 1697번 문제풀이 (0) | 2021.02.11 |
[C++] 백준 1620번 문제풀이 (0) | 2021.02.11 |