[BOJ 7577 // C++] 탐사

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 7577번 문제인 탐사이다.
문제는 아래 링크를 확인하자.

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

7577번: 탐사

Si 를 0번부터 i번 칸까지의 탐사선 개수라고 하자.

 

각 칸에는 탐사선이 있거나 없거나의 두 가지중 하나의 상태이다. 따라서 0 <= S(i+1) - Si <= 1이 성립한다.

또한 문제에서 주어지는 "x부터 y까지 구간에 있는 탐사선 수 C"는 C <= Sy - S(x-1) <= C와 같이 부등식으로 표현할 수 있다.

 

탐사선의 배치는 위의 부등식들만을 만족하면 되므로, 위의 system을 풀어주면 문제를 해결할 수 있다.

위의 꼴의 부등식들은 Bellman-Ford 알고리즘으로 풀이가 가능하므로 이를 이용하여 해결하자.

 

실제 탐사선의 배치를 역추적할 때는 Si가 변하는 지점에 탐사선을 배치해주면 된다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <string>
using namespace std;
typedef long long ll;

struct edge {
	int x, y;
	ll d;
	edge(int x, int y, ll d) {
		this->x = x, this->y = y, this->d = d;
	}
};

ll dist[41];
vector<edge> edges;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int K, N; cin >> K >> N;
	while (N--) {
		int x, y, r; cin >> x >> y >> r;
		edges.emplace_back(edge(x - 1, y, r));
		edges.emplace_back(edge(y, x - 1, -r));
	}
	for (int i = 0; i < K; i++) {
		edges.emplace_back(i, i + 1, 1);
		edges.emplace_back(i + 1, i, 0);
	}

	for (int i = 1; i <= K; i++) dist[i] = 1000000007;

	for (int i = 0; i < K; i++) {
		for (auto &e : edges) {
			if (e.x < 1000000007) dist[e.y] = min(dist[e.y], dist[e.x] + e.d);
		}
	}

	bool chk = 1;
	for (auto& e : edges) {
		if (e.x < 1000000007) {
			if (dist[e.y] > dist[e.x] + e.d) chk = 0;;
		}
	}

	if (chk) {
		string ans = "";
		for (int i = 1; i <= K; i++) {
			if (dist[i - 1] < dist[i]) ans += '#';
			else ans += '-';
		}
		cout << '\n' << ans;
	}
	else cout << "NONE";
}