백준 1219 오민식의 고민 C++ 풀이 - BFS, Bellman-Ford

기민이의 고민을 만들어준 짜증나는 문제 원탑이다.
시작하자마자 틀린 것은 type 선언 문제가 컸고,
17% 혹은 18%에서 틀린 것은 사이클이 여러개 있다는 것을 간과해서 그럴 수 있다.

만약 벨만포드 알고리즘을 사용할 것이라면
1. 사이클 유무 확인
2. 사이클마다 목표지점에 닿는지 확인

두 가지를 필수로 사용해야 한다.

나는 도로를 지나가는데 사용한 비용을 음수로 넣고 city 에서 얻을 수 있는 돈을 city 배열에 저장해서
단순히 + 연산으로만 구현할 수 있게 만들었고,
초반에 distance 구하는 건 줄 알고 dist 배열로 선언한 것을 그냥 총 벌어들인 돈 배열로 생각하기로 했다.

예제에서는 다음과 같은 사실을 발견해야 한다.
1. 자기 자신으로 가는 간선이 존재한다. (dist[S] = city[S] 로 만들어두고 시작)
2. 벨만 포드는 음수 사이클을 찾을 수 있지만, 또한 무한대로 발산하는 배열도 찾을 수 있다.(반대로 생각)
3. 사이클 안에 E(목표노드)가 있거나, 사이클과 연결되어 있으면 무한대로 벌 수 있다.

예제에서 발견할 수 없는 사실은 다음과 같다.
1. dist 배열은 최대 10^6의 값이 N * N * E 번 접근할 수 있기 때문에 long long 으로 다뤄야 한다.
2. 사이클이 여러개 있을 경우도 생각해야 한다.

위 5가지를 명심하고 벨만포드로 접근하면 쉽게 풀 수 있다.

벨만 포드는 N개의 노드를 순회하며 모든 간선에 대해 연결시켜보는 건데
최단거리는 항상 N-1개의 간선으로 이루어져 있으므로(음수 사이클 없을 때)
N-1 번 반복해서 N개의 노드를 순회하며,
N 번 반복했을 때 업데이트 되는 노드가 있다면 음수 사이클의 존재가 증명된다.

#include <cstdio>
#include <vector>
#include <queue>
#define INF 987654321
using namespace std;

int N, M,S,E, u,v, p, c;
vector<pair<int, int>> edge[101];
int city[101];
long long dist[101];

int bfs(int S, int E) {
	if (S == E) return 1;
	int visited[101] = { 0 };
	queue<int> q;
	q.push(S);
	visited[S] = 1;
	while (!q.empty()) {
		int cur = q.front(); q.pop();
		for (int i = 0; i < edge[cur].size(); i++) {
			int next = edge[cur][i].second;
			if (visited[next]) continue;
			visited[next] = 1;
			if (next == E) return 1;
			q.push(next);
			
		}
	}
	return 0;
}
// 사이클이 여러개 있을 수도 있어서 사이클마다 E로 갈 수 있는지 체크
// 갈 수 있으면 그 node 번호 return
// 갈 수 없으면 -1 return
int bellman(int S, int isCycle) {
	dist[S] = city[S];
	for (int j = 0; j < N-1 + isCycle; j++) {
		for (int k = 0; k < N; k++) {

			if (dist[k] == -INF) continue;
			for (int i = 0; i < edge[k].size(); i++) {
				int next_node = edge[k][i].second;
				int next_cost = edge[k][i].first;
				if (dist[next_node] >= dist[k] + next_cost + city[next_node]) continue;
				dist[next_node] = dist[k] + next_cost + city[next_node];
				if (j == N - 1) {
					if (bfs(next_node, E)) return next_node;
				}
			}
		}
	}
	return -1;
}



int main() {
	scanf("%d %d %d %d", &N, &S, &E, &M);
	edge->clear();
	for (int i = 0; i < M; i++) {
		scanf("%d %d %d", &u, &v, &p);
		edge[u].push_back({ -p,v });
	}
	for (int i = 0; i < N; i++) {
		scanf("%d", &city[i]);
	}

	fill_n(dist, sizeof(dist) / sizeof(long long), -INF);
	//무한대로 늘 수 있는지 사이클 확인
	int isInf = bellman(S, 1);
	// 갈 수 없으면 gg
	if (dist[E] == -INF) {
		printf("gg\n");
	}//갈 수 있는데 cycle 존재하는 경우
	else if (isInf!=-1) {
		printf("Gee\n");
	}//갈 수 있고 cycle 없는 경우
	else {
		printf("%lld\n", dist[E]);
	}

	return 0;
}