백준 1956번 _ 운동

2020-04-03 · 배운 것 · 3분 읽기

https://www.acmicpc.net/problem/1956

1956번: 운동

1. 풀이 방법

V : 정점, E : 간선

1) 구하려는 것 : 모든 사이클에서의 최단거리 ( ex) 1 -> 2 ->1 가능 )
2) 구하기 위해 필요한 도구 : 정점에서 다른 정점까지의 최단거리
3) 모든 정점에서의 최단거리를 구할때는 -> 플로이드 와샬 알고리즘 ( V^3 )
4) 구한 이차배열을 순회하며 갔다올때 가장 적은 경로를 가지는 값 출력 ( V*( V - 1 ) )

2. 코드

#include <iostream>
#include <algorithm>
#include <vector>

#define INF 987654321

using namespace std;

int floyed[402][402];
int v, e;
//이어진노드, 거리
vector<vector<pair<int,int>>> edge;

int main()
{
	cin >> v >> e;
	edge.resize(v + 2);
	//folyed init
	for(int i =1; i<=v; i++)
		for (int j = 1; j <= v; j++)
		{
			if (i == j)
				continue;
			floyed[i][j] = INF;
		}

	//input
	int a, b, c;
	for (int i = 0; i < e; i++)
	{
		cin >> a >> b >> c;
		edge[a].push_back({ b, c });
		floyed[a][b] = min(floyed[a][b], c);
	}

	//foyed ㄱㄱ
	for(int mid = 1; mid<=v; mid++)
		for (int start = 1; start <= v; start++)
		{
			if (start == mid)
				continue;
			for (int end = 1; end <= v; end++)
			{
				//시작점과 끝점이 같거나, 중간점과 끝점이 같을때
				if (start == end || end == mid)
					continue;

				int comp = floyed[start][mid] + floyed[mid][end];
				floyed[start][end] = min(floyed[start][end], comp);
			}
		}

	//최소 사이클 찾기
	int answer = INF;
	for(int i=1; i<=v; i++)
		for (int j = i + 1; j <= v; j++)
		{
			answer = min(floyed[i][j] + floyed[j][i], answer);
		}

	if (answer >= INF)
		cout << -1;
	else
		cout << answer;

	return 0;
}

3. 후기

플로이드 와샬 알고리즘만 숙지하고 있다면 쉬운 문제였다.