[BOJ 7634 // C++] Guessing Game

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

 

이번에 볼 문제는 백준 7634번 문제인 Guessing Game이다.
문제는 아래 링크를 확인하자.

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

7634번: Guessing Game

문제에서 주어지는 모든 조건은 ai + bj (>= 또는 <=) c 꼴을 하고 있다.

한편, 모든 ai들은 +를 기준으로 왼쪽에, bj들은 오른쪽에 있으므로, bj에 저장된 숫자들에 전부 -1을 곱한 b'j를 이용하면 식을 ai - b'j >= c 또는 ai - b'j <= c의 꼴로 바꿔쓸 수 있다.

 

이 바뀐 식들은 Bellman-Ford를 이용하여 해를 구할 수 있는 system이 된다.

 

가상의 노드(0번 노드)에서 모든 노드로 향하는 가중치 0인 에지가 있다고 생각하고 모델링을 하면 모든 노드의 dist를 0으로 한 상태에서 모든 노드를 갱신하는 식으로 Bellman-Ford를 구현할 수 있다. 이 그래프에서 negative cycle을 찾는 것으로 주어진 system의 해가 존재하는지 여부를 판단할 수 있다.

 

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

#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;
	}
};

int N, M, Q;
vector<edge> edges;

void solve() {
	edges.clear();
	while (Q--) {
		int x, y, d; string s; cin >> x >> y >> s >> d;
		y += N;
		if (s[0] == '<') edges.emplace_back(edge(y, x, d));
		else edges.emplace_back(edge(x, y, -d));
	}
	N += M;

	vector<ll> dist(N + 1, 0);
	dist[0] = 0;
	for (int i = 1; i < N; i++) {
		for (auto &e : edges) {
			dist[e.y] = min(dist[e.y], dist[e.x] + e.d);
		}
	}

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

	if (chk) cout << "Possible\n";
	else cout << "Impossible\n";
}

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

	cin >> N >> M >> Q;
	while (N) {
		solve();
		cin >> N >> M >> Q;
	}
}