백준 1219 c++ "오민식의 고민" -PlusUltraCode-

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

 

 

 

 

[필자 사고]

 

1. 무한히 돈을 벌 수 있다 << 양수 사이클

2. 도착 도시를 도착했을 때 최대로 돈 벌수 있는 경우 << 모든 경로를 돌아 매번 값을 최대값으로 갱신

=> 벨만포드를 이용하면 특정 위치로부터 모든 경로를 탐색할 수 있게 된다.

 

이 문제에서 실수하기 쉬운 부분은 long 이다. 비용 관련 자료형은 long 으로 다 바꿔줘야 된다.

또한 시작도시는 반드시 haveMoneys[start] = money[start] 를 해야된다.

움직이지 않아도 현재 있는 도시니깐 초기화를 위와 같이 해줘야 된다.

 

아래는 코드 풀이다.

 

• Input() 함수
  • 노드의 수 N, 시작점 S, 목표점 E, 그리고 간선의 수 M을 입력받는다.
  • money 벡터는 각 노드에서 얻을 수 있는 수익을 저장하며, haveMoneys 벡터는 각 노드에서 시작점으로부터 얻을 수 있는 최대 수익을 저장한다.
  • 이후 M개의 간선 정보를 입력받아, 각각의 시작 노드, 끝 노드, 그리고 시간 비용을 구조체 Node로 저장한다.
  • 마지막으로, 각 노드에서 얻을 수 있는 수익 정보를 입력받는다.
• BelManFord() 함수
  • 벨만-포드 알고리즘을 사용하여 최대 수익을 계산하는 방식이다.
  • haveMoneys[S]는 시작점에서 얻을 수 있는 초기 수익으로 설정되며, 이는 money[S] 값이다.
  • N+50번 반복하여 간선들을 확인하는데, 이를 통해 노드 간 수익을 갱신한다.
  • 각 간선에서 start 노드에서 end 노드로 가는 경우, 현재 수익에 해당 노드의 수익을 더하고 시간 비용을 빼서 더 큰 수익이 발생하면 값을 갱신한다.
  • 만약 반복 횟수가 N 이상이면 양수 사이클이 존재할 수 있으므로, 해당 경로는 무한대로 처리하기 위해 haveMoneys[end]를 LONG_MAX로 설정한다.
• GameStart() 함수
  • BelManFord() 함수를 호출하여 최대 수익을 계산한 후, 목표점 E에서의 상태를 확인하는 방식이다.
  • 만약 목표점에 도달할 수 없다면 gg를 출력한다.
  • 만약 목표점이 음수 사이클에 속해 무한대 수익이 발생하는 경우 Gee를 출력한다.
  • 그렇지 않다면 목표점에서 얻을 수 있는 최대 수익을 출력한다.

 

 

 

 

[소스 코드]

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

struct Node {
	int start;
	int end;
	long time;
};

vector<Node> arr;
int N, S, E, M;
vector<long> money;
vector<long> haveMoneys;

void Input() {
	cin >> N >> S >> E >> M;

	money.resize(N);
	haveMoneys.resize(N,LONG_MIN);
	for (int i = 0; i < M; i++) {
		int s, e;
		long w;
		cin >> s >> e >> w;
		arr.push_back({ s,e,w });
	}

	for (int i = 0; i < N; i++) {
		cin >> money[i];
	}
}

void BelManFord() {
	haveMoneys[S] = money[S];
	for (int i = 0; i <= N+50; i++) {
		for (int k = 0; k < M; k++) {
			Node node = arr[k];
			int start = node.start;
			int end = node.end;
			long time = node.time;
			if (haveMoneys[start] == LONG_MIN)continue;
			if (haveMoneys[start] == LONG_MAX) {
				haveMoneys[end] = LONG_MAX;
				continue;
			}
			if (haveMoneys[end] < haveMoneys[start] + money[end] - time) {
				haveMoneys[end] = haveMoneys[start] + money[end] - time;

				if (i >= N - 1) {
					haveMoneys[end] = LONG_MAX;
				}
			}
		}
	}
}

void GameStart() {
	BelManFord();

	if (haveMoneys[E] == LONG_MIN) {
		cout << "gg";
		return;
	}
	if (haveMoneys[E] == LONG_MAX) {
		cout << "Gee";
		return;
	}
	
	cout << haveMoneys[E];
}

int main(void) {
	Input();
	GameStart();
}