전형적인 플로이드워셜 알고리즘... dfs/bfs 분류에도 속해있다는데 그것도 대충 로직은 그려진다. 이전에 촌수계산 문제 풀었을 때와 비슷한 문제인 것 같다. 일단 오늘 학습한 내용으로 풀었는데 나중에 bfs 연습문제로 풀어보면 좋을 것 같다.
삼중반복문 돌려서 최단거리 테이블을 완성시킨 뒤에 각 노드마다 다른 노드로 가는 모든 거리를 더한 값을 min값과 비교했다. 그래서 바뀌면 그게 min임. 그때의 노드 번호를 출력하도록 작성했다.
#include <iostream>
using namespace std;
#define INF 1e9
int graph[101][101];
int main()
{
int n, m;
cin >> n >> m;
for (int i = 0; i < 101; i++)
{
for (int j = 0; j < 101; j++)
{
graph[i][j] = INF;
if (i == j)
graph[i][j] = 0;
}
}
for (int i = 0; i < m; i++)
{
int a, b;
cin >> a >> b;
graph[a][b] = 1;
graph[b][a] = 1;
}
for (int i = 1; i <= n; i++)
{
for (int a = 1; a < 101; a++)
{
for (int b = 1; b < 101; b++)
{
graph[a][b] = min(graph[a][b], graph[a][i] + graph[i][b]);
}
}
}
int sum, ans;
int min = INF;
for (int i = 1; i <= n; i++)
{
sum = 0;
for (int j = 1; j <= n; j++)
sum += graph[i][j];
if (sum < min)
{
min = sum;
ans = i;
}
}
cout << ans << endl;
}
새벽에 최단경로 문제를 너무 급하게 공부한 것 같아서 재정리할 겸 다시 풀어봤다. 새벽에 푼 문제보단 어려운 난이도였지만 근본적으로 최단경로를 구하는 방법은 같았고 작은 아이디어 하나만 있으면 돼서 무난하게 푼 문제다. 플로이드워셜 알고리즘을 알고있다면 이 문제는 입력받는 방법만 신경쓰면 된다.
#include <iostream>
#define INF 1e9
using namespace std;
int graph[101][101];
int n, m;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
graph[i][j] = INF;
}
}
for (int i = 0; i < m; i++)
{
int a, b, value;
cin >> a >> b >> value;
if (graph[a][b] > value)
graph[a][b] = value;
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j < 101; j++)
{
for (int k = 1; k < 101; k++)
{
graph[j][k] = min(graph[j][k], graph[j][i] + graph[i][k]);
}
}
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (graph[i][j] == INF || i == j)
cout << "0" << ' ';
else
cout << graph[i][j] << ' ';
}
cout << '\n';
}
}