[백준] 1956 운동(C++)

[백준] 1956 운동(C++)

백준 1956 운동

1. 문제

문제링크

2. 접근법

문제 접근 도로의 길이 합이 가장 작은 사이클을 찾아야 하므로 거쳐가는 노드를 잡고 최솟값을 갱신해주어야 한다. 따라서 플로이드 와샬 알고리즘을 사용하면 된다. 플로이드 와샬로 최솟값을 갱신해준 뒤 이중 for문을 돌리면서 사이클을 형성하는 두 마을의 최소거리를 구하면 된다.

3. 코드

#include #include #include #include using namespace std; int map[401][401]; //플로이드 와샬 알고리즘을 사용하여 한 노드를 거쳐가는 경우 최단거리를 갱신해주고 //이중for문으로 map을 돌면서 a->b, b->a에 값이 존재하는 경우 최솟값을 구해주면 된다. int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int MIN = 987654321; int temp = MIN; int v, e, a, b, c; cin >> v >> e; //전체 map을 temp로 초기화 for (int i = 0; i < v; i++) { for (int j = 0; j < v; j++) { map[i][j] = temp; } } for (int i = 0; i < e; i++) { cin >> a >> b >> c; map[a-1][b-1] = c; } //플로이드 와샬 for (int k = 0; k < v; k++) { for (int i = 0; i < v; i++) { for (int j = 0; j < v; j++) { if (map[i][j] > map[i][k] + map[k][j]) { map[i][j] = map[i][k] + map[k][j]; } } } } for (int i = 0; i < v; i++) { for (int j = 0; j < v; j++) { if (i == j) continue; //값이 존재하는 경우 min에 최단거리 갱신 if (map[i][j] != temp && map[j][i] != temp) { MIN = min(MIN, map[i][j] + map[j][i]); } } } //MIN에 새로운 값이 갱신되었으면 갱신된 값 출력, 아니면 -1 출력 if (MIN != temp) cout << MIN << "

"; else cout << -1 << "

"; return 0; }

4. 시간복잡도

문제에서 주어진 노드는 최대 400개이고 간선은 400*399=159600개이다.

플로이드 와샬을 사용하면 400*400*400 = 64,000,000으로 1초를 넘지 않고, 플로이드 와샬을 제외한 부분들도 최대가 이중 for문이라 모두 더해도 2억을 넘지 않으므로 2초내에 구현하기 충분하다.

5. 결과

from http://pro-grammers.tistory.com/25 by ccl(A) rewrite - 2021-08-12 21:26:05