백준 : 3176번 도로 네트워크, 11657번 타임머신(벨만포드)

3176번

 

https://m.blog.naver.com/PostView.nhn?blogId=jh20s&logNo=221339300027&proxyReferer=https%3A%2F%2Fwww.google.com%2F

 

LCA(Lowest Common Ancestor) 최소 공통 조상 알고리즘

 

위 블로그를 참고했다.ㅍ

 

문제 추가. https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LnipaDvwDFAXc

SW Expert Academy

이것도 풀어보자.

 

일단 위의 문제를 푸는데 실패 했다. 왜 틀린지 잘 모르겠다......

 

 

 

 

11675번 벨만 포드..... 

벨만 포드 원리를 읽고 구현하는데 자꾸 틀린다. 제대로 이해 못한거 같다.

 

#include <iostream>
#include <string.h>
#include <cstring>
#include <algorithm>
#include <vector>
#define NUM 100005
#define INF 50000001
int N, K, M;

using namespace std;

int dist[501] = { 0 };
int adj[501][501];


int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	freopen("input.txt", "r", stdin);

	cin >> N >> M;

	//memset(adj, -1, sizeof(adj));
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++)
		{
			adj[i][j] = INF;
		}
		dist[i] = INF;
	}


	for (int i = 0; i < M; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		if( c < adj[a][b])
			adj[a][b] = c;
	}

	dist[1] = 0;

	int ans[501];
	bool flag = true;

	for (int i = 0; i < 2; i++) {
		for (int src = 1; src <= N; src++) {
			for (int dst = 1; dst <= N; dst++) {
				if ( dist[src] != INF && adj[src][dst] != INF) {
					if (i == 1) {
						int ren = dist[src] + adj[src][dst];
						if (ren < dist[dst])
							flag = false;
					}
					else 
						dist[dst] = min(dist[src] + adj[src][dst], dist[dst]);
				}				
			}
		}
	}
	
	//if (dist[1] < 0)
	//	flag = false;
	
	if (flag == false) {
		cout << -1; 
	}
	else {
		for (int i = 2; i <= N; i++) {
			if (dist[i] != INF)
				cout << dist[i] << "\n";
			else
				cout << -1 << "\n";
		}
	}


	return 0;
}

 

참고 블로그 : https://codemcd.github.io/algorithm/Algorithm-%EB%B2%A8%EB%A7%8C-%ED%8F%AC%EB%93%9C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98/ 

벨만-포드(Bellman-Ford)의 최단 경로 알고리즘

시작점에서 정점 u까지 가는 최단 경로는 항상 upper[u]보다 작거나 같다.(upper배열은 상한을 저장하는 배열이기 때문) 여기서 정점 u에서 정점 v까지 가는 최단 경로는 더하면 upper[u] + w(u, v)이며, 이 거리가 upper[v]보다 짧으면 이를 갱신한다. 이러한 과정을 통해 upper[v]를 감소하는 작업을 (u, v)에 따라 완화(relax)한다고 한다.

 

그래 완화가 뭔지는 알겠다......

 

벨만-포드 알고리즘은 이와 같은 완화 과정을 모든 간선에 대해 반복적으로 수행한다. 음수 사이클이 없는 그래프에서 최단 경로는 한 정점을 두 번 지난 일이 없으므로, V개의 정점 그래프에서 최단 경로를 나타내는 간선의 개수는 V - 1개 이다. 따라서, 모든 간선에 대한 완화 과정은 V - 1번 수행하면 시작점을 제외한 모든 정점까지 최단 경로를 계산할 수 있다.

 

이 부분을 이해잘 못했다. 최소 스패닝 트리로 만들면 위의 완화 과정이 V-1번 필연적으로 발생한다는 말같다. 노드 V개의 간선 V-1개인 최소 스패닝 트리가 만들어 지겠지!! 그러므로 이제 아래가 이해 된다.

 

음수 사이클 판정

음수 사이클이 존재하는 그래프는 최단 거리를 구할 수 없다.(무한히 거리가 작아지기 때문이다.) 그러므로 벨만-포드 알고리즘은 음수 사이클이 존재한다면 의미없는 값을 반환해야 한다. 그러면 음수 사이클이 있는지 어떻게 판단할까? 위에서 완화 과정은 V - 1번 수행하면 모든 최단 경로를 찾을 수 있다고 하였다. 하지만 음수 사이클이 존재한다면 이 이후에도 계속 거리가 줄어들어 완화가 진행될 것이다. 따라서, 벨만-포드 알고리즘은 음수 사이클이 존재하는지 판단하기 위해 총 V번 동안 모든 간선에 대해 완화 과정을 수행한다.

 

간선 완화를 딱 한번 더 해보면 된다는 말이다. 근데 V-1 번 완화 한걸 어떻게 구하냐....아 구현을 못하겠네 해보자 그래도 맨날 코드 배끼고 이해한줄 알았는데 지금 처럼 백지로 하려니까 실패한다. 세밀한 부분에 이해가 부족해서 벨만포드를 이해하지 못한거 같다. 위에서 말한 최소 스패닝 트리를 만드는데 필요한 완화 횟수가 V-1번임을 몰랐다.... 그래서 음수 사이클 확인을 왜 V 번 해야 알 수 있는지도 몰랐고

 

 

 

 

#include <iostream>
#include <string.h>
#include <cstring>
#include <algorithm>
#include <vector>
#define NUM 100005
#define INF 50000001
int N, K, M;

using namespace std;

int dist[501] = { 0 };
int adj[501][501];


int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	freopen("input.txt", "r", stdin);

	cin >> N >> M;

	//memset(adj, -1, sizeof(adj));
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++)
		{
			adj[i][j] = INF;
		}
		dist[i] = INF;
	}


	for (int i = 0; i < M; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		if( c < adj[a][b])
			adj[a][b] = c;
	}

	dist[1] = 0;

	int ans[501];
	bool flag = true;

	for (int i = 1; i <= N; i++) {
		for (int src = 1; src <= N; src++) {
			for (int dst = 1; dst <= N; dst++) {
				if (dist[src] != INF && adj[src][dst] != INF) {
					int ren = dist[src] + adj[src][dst];

					if (ren < dist[dst]) {
						dist[dst] = ren;
						if(i== N)
							flag = false;
					}
					
				}
			}
		}
	}



	
	//if (dist[1] < 0)
	//	flag = false;
	
	if (flag == false) {
		cout << -1; 
	}
	else {
		for (int i = 2; i <= N; i++) {
			if (dist[i] != INF)
				cout << dist[i] << "\n";
			else
				cout << -1 << "\n";
		}
	}


	return 0;
}

 위 처럼 다시 해서 맞았다......

 

	//간선 완화 횟수를 N-1 번에 1번 더하고 1번 더 했을때 완화 또 되면 음수 사이클~~
	for (int i = 1; i <= N; i++) {
		//간선 완화중
	}