백준 1956_운동 문제풀이 in C++
문제 URL
https://www.acmicpc.net/problem/1956
문제 요구사항
- V개의 마을과 E개의 도로로 구성되어 있는 도시가 있다. 도로는 마을과 마을 사이에 놓여 있으며, 일방 통행 도로이다.
- 도로를 따라 운동을 하기 위한 경로를 찾으려고 한다. 운동을 한 후에는 다시 시작점으로 돌아오는 것이 좋기 때문에, 우리는 사이클을 찾기를 원한다.
- 사이클을 이루는 도로의 길이의 합이 최소가 되도록 찾으려고 한다.
- 도로의 길이의 합이 가장 작은 사이클을 찾는 프로그램을 작성하라.
- 첫째 줄에 V와 E가 빈칸을 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1))
- 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다.
- a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의미이다.
- (a → b임에 주의) 거리는 10,000 이하의 자연수이다. (a, b) 쌍이 같은 도로가 여러 번 주어지지 않는다.
접근 방법
- 3개의 반복문을 중첩하여, 각각의 반복 인자를 거쳐가는 정점, 출발 정점, 도착 정점으로 사용하여 탐색한다.
풀이 순서
- V와 E 값을 입력 받는다
- 전역 변수로 선언해둔 map[402][402]를 V 크기만큼 INF(987654321) 값으로 초기화 한다.
- E의 크기만큼 반복하여, a(출발 정점), b(도착 정점), c(가중치) 값을 입력 받아 map[a][b] = c로 값을 저장한다.
- 3개의 반복문을 사용한다.
- k는 거쳐가는 정점을 의미 한다.
- i는 출발 정점을 의미 한다.
- j는 도착 정점을 의미 한다.
- map[i][j] ( i 출발 j 도착) 값이 map[i][k] + map[k][j] (i출발 k를 거쳐 j로 도착) 값보다 크면 map [i][j]값을 갱신해준다.
- V 크기만큼 반복하여 map[i]i값이 result(초기값 INF)보다 작으면 result 값을 갱신 해준다.
- result 값 출력, 만약 result 값이 INF라면 -1 출력
소스코드
#include <iostream>
using namespace std;
#define INF 987654321
int V, E;
int map[402][402];
void input() {
cin >> V >> E;
for (int i = 1; i <= V; i++) {
for (int j = 1; j <= V; j++) {
map[i][j] = INF;
}
}
for (int i = 0; i < E; i++) {
int a, b, c;
cin >> a >> b >> c;
map[a][b] = c;
}
}
void solution() {
// k = 거쳐가는 정점
for (int k = 1; k <= V; k++) {
// i = 출발 정점
for (int i = 1; i <= V; i++) {
// j = 도착 정점
for (int j = 1; j <= V; j++) {
if (map[i][j] > map[i][k] + map[k][j]) {
map[i][j] = map[i][k] + map[k][j];
}
}
}
}
}
void output() {
int result = INF;
for (int i = 1; i <= V; i++)
result = (result < map[i][i]) ? result : map[i][i];
if (result == INF) {
cout << "-1" << "\n";
}
else {
cout << result << "\n";
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
input();
solution();
output();
return 0 ;
}
문제 풀이 결과
