c++/알고리즘

[c++] 백준-1956 운동 (플로이드 워셜)

hojung 2023. 2. 7.

728x90

1. 문제

2. 입출력 및 예제

3. 문제 해설

플로이드 워셜 알고리즘에서 사이클을 찾는 문제였다.

플로이드 알고리즘은 2차원 배열을 선언해두고 진행하는데 대각선에 있는 값들은 대게 0으로 초기화해두고 진행하는 것이 일반적이다. 하지만 이는 사이클이 존재하지 않을 때에 해당하고 사이클이 존재한다면 자기 자신으로 돌아오는 경우의 수가 있기 때문에 2차원 배열의 대각선 값이 0이 되지 않고 다른 값으로 변할 것이다. 따라서 조건을 추가해주어햐 하는 것들이 존재한다.

0	INF	INF
INF	0	INF
INF	INF	0

플로이드 알고리즘은 위와 같이 정사각형의 배열을 대각선의 값은 0 대각선을 제외한 값은 INF(무한대)값으로 초기화해두고 진행한다.

그 후 입력을 받으면 배열이 다음과 같이 된다. (플로이드 알고리즘은 방향이 있는 경우와 없는 경우 둘 다 가능하다.)

예제를 한 번 수행해보겠다.

0	1	5
INF	0	2
INF	1	0

만약 예제처럼 연결되어 있는 모든 간선들을 입력받으면 위와 같이 거리 배열이 초기화될 것이다.

배열 dist[i][j]의 의미는 i번 노드에서 j번 노드로 갈 수 있는 최단 거리를 의미한다.

못가는 경우는 무한대 값이다.

그 후 플로이드 알고리즘은 경유지 값 K를 1에서 N까지 증가시키며 진행한다.

dist[i][j] = min(dist[i][j] , dist[i][k] + dist[k][j])

위의 로직은 현재 경로로 가는 거 보다 k를 거쳐서 갈 때 거리가 더 적다면 업데이트하라라는 의미이다.

위의 계산식에서 자기 자신으로 돌아오는 경우를 생각해보자

그러면 초기화된 값이 0이고 음의 가중치가 존재하지 않으므로 항상 0이 작은 값이 되어 변하지 않을 것이다.

위의 문제를 해결해주기 위해 대각선의 경우와 그렇지 않은 경우를 나눠주었다.

대각선이 아닌 경우

일반적인 플로이드 알고리즘처럼 위와 같이 초기화 된 상태에서

dist[i][j] = min(dist[i][j] , dist[i][k] + dist[k][j])

위의 로직을 사용해 진행해주면 된다.

대각선의 경우

대각선의 값을 INF로 초기화 해준 후 플로이드 로직을 수행해야한다.

또한 경유지 k가 i와 같을 경우 i==k==j가 되므로 거리가 2 * dist[i][j]가 될 수 있기 때문에 k와 i가 같은 경우도 고려해주어야 한다.

for (int k = 1; k <= V; k++) {
		for (int i = 1; i <= V; i++) {
			for (int j = 1; j <= V; j++) {
				if (i != j) { // 대각선이 아닌 경우
					if (i == k) {
						dist[i][j] = min(dist[i][j], dist[k][j]); // 만약 경유지 k가 i와 같다면 0으로 계산해준다. 
					}
					else if (k == j) { //경유지 k와 j가 같다면 0으로 계산해준다. 
						dist[i][j] = min(dist[i][j], dist[i][k]);
					}
					else dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); // 다른 경우는 일반적인 플로이드 식을 사용한다.
				}
				else { // 대각선의 경우
					if (dist[i][j] == 0) {
						dist[i][j] = INF; // 최소 값을 구해야하므로 무한대 값으로 초기화
					}
					if (i != k) { // 만약 k가 i나 j와는 다른 값이라면 일반적인 플로이드 로직
						//printf("dist[%d][%d] : %lld  dist[%d][%d] : %lld dist[%d][%d] : %lld\n", i, j, dist[i][j], i, k, dist[i][k], k, j, dist[k][j]);
						dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
						//printf("dist[%d][%d] : %lld\n", i, j, dist[i][j]);
					}
					if (dist[i][j] >= INF) dist[i][j] = 0; 대각선의 값이 변하지 않았다면(사이클을 갖지 않는다면) 다시 INF -> 0으로 초기화
				}
			}
		}
	}

4. 코드

#pragma warning (disable : 4996)
/*
	플로이드 워셜 알고리즘에서 사이클을 찾는 법
	대각선의 값을 살펴보면 된다. 
	자기 자신으로 돌아오는 경우 대각선의 값이 갱신된다. 
*/
#include <cstdio>
#include <algorithm>
#define MAX 402
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
int V, E; // 노드와 간선 수 
ll dist[MAX][MAX]; // 3 * 400 * 400 = 480000 = .0.48MB
ll mins = INF;
void input() {
	scanf("%d %d", &V, &E);

	for (int i = 1; i <= V; i++) {
		for (int j = 1; j <= V; j++) {
			if (i != j) {
				dist[i][j] = INF;
			}
		}
	} // 무한대로 초기화
	for (int i = 0; i < E; i++) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		dist[a][b] = c; // 거리 배열 초기화
	}
}

void sol() {
	for (int k = 1; k <= V; k++) {
		for (int i = 1; i <= V; i++) {
			for (int j = 1; j <= V; j++) {
				if (i != j) {
					if (i == k) {
						dist[i][j] = min(dist[i][j], dist[k][j]);
					}
					else if (k == j) {
						dist[i][j] = min(dist[i][j], dist[i][k]);
					}
					else dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
				}
				else {
					if (dist[i][j] == 0) {
						dist[i][j] = INF;
					}
					if (i != k) {
						//printf("dist[%d][%d] : %lld  dist[%d][%d] : %lld dist[%d][%d] : %lld\n", i, j, dist[i][j], i, k, dist[i][k], k, j, dist[k][j]);
						dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
						//printf("dist[%d][%d] : %lld\n", i, j, dist[i][j]);
					}
					if (dist[i][j] >= INF) dist[i][j] = 0;
				}
			}
		}
	}

	for (int i = 1; i <= V; i++) {
		if (dist[i][i] != 0) {
			mins = min(mins, dist[i][i]);
		}	
	}

	printf("%lld\n", mins < INF ? mins : -1);
}
int main() {
	input();
	sol();
	return 0;
}