프로젝트를 진행하는 한편 코딩테스트도 소홀히 할 수는 없어 매일 한 문제씩은 풀고 있습니다. 이번에 풀어본 문제는 적당히 도전적인 걸로 골랐습니다. 백준 1페이지의 물약입니다.

언뜻 문제를 읽어보면 그냥 문자열 뜯는 게 귀찮고 풀이 자체는 쉽다고 생각할 수도 있습니다. 저도 입출력 받는 거 연습이나 하자 싶어서 풀려고 했는데요. 하지만 조금만 깊게 따져본다면 마냥 간단히 풀리지만은 않습니다.

시장 가격보다 조합 가격이 쌀 수 있습니다. 이건 그냥 업데이트 해주면 되는 거 아닌가 싶지만, dfs나 bfs 등을 돌리면서 불필요한 탐색을 줄이고자 하다가 최적 조합식을 놓칠 수 있습니다.

또한 하나의 물약을 만드는 데 조합식이 둘 이상 존재할 수 있습니다. 예제 입력 8번이 그러한데, 어떤 조합식을 쓰는가에 따라 가격이 달라집니다. 그래프 탐색 시 정점을 분리하여 돌릴 필요가 있다는 뜻이 됩니다.

조합식끼리 순환참조 하는 경우가 있을 수 있습니다. 예제 입력 5번이 해당 경우로, FIRST와 SECOND는 다른 조합식이 존재하지 않는 한 어느 한 쪽도 만들 수 없습니다. 그래프 탐색 시 사이클 디텍션까지 고려해야 합니다.

처음엔 위상정렬이나 단절점처럼 특수한 그래프 탐색 기법을 써서 풀어볼까 싶었는데요. 물론 그렇게 해서도 답이 나올 수는 있지만 더 쉬운 방법도 있습니다. 조합식의 수는 많아야 50개이고 그 길이도 각각 50이 넘지 않으므로 시간복잡도를 그렇게 빡빡하게 생각할 필요는 없어보입니다.

여기서 언뜻 스쳐지나간 건 벨만-포드 알고리즘이었습니다. 물론 약간 다르긴 한데, 최적 조합 가격을 찾는 업데이트를 충분히 반복하다보면 답이 나오지 않을까 하는 것이죠. 풀이는 간단한데요, \(M\)개의 조합식에 대해 각각 가격을 구하여 최소값을 업데이트 합니다. 그걸 충분히 많이 해주면 됩니다.

그럼 얼마나 많이 하면 될까요? \(M\)번이면 충분합니다. 논의를 단순화하기 위해 최소 가격이 구해진 경우 그 정점을 방문 완료했다고 하겠습니다.

  • 어떤 물약이 시장에서 팔고 있고, 조합식이 없을 경우 (리프 노드) 방문 완료입니다.
  • 어떤 조합식의 모든 항이 방문 완료일 경우 그 조합식은 더 이상 가격이 낮아지지 않고, 그 때의 가격이 최적입니다.
  • 어떤 물약의 모든 조합식이 최적일 때, 그 중 최소 가격을 구할 수 있고 그 경우 방문 완료입니다.

그리고 잘 생각해보면 다음 명제가 참이 됩니다.

  • 한 번의 업데이트에 대해, 최소 한 개의 조합식은 최적이 됩니다.
  • 조합식의 수 \(M\)만큼 업데이트를 하면 모든 정점은 방문 완료됩니다.

위 명제가 참이 되지 않는 경우는 리프 노드가 아예 없거나 순환참조가 이루어져 어느 하나를 먼저 만들 수 없을 때입니다. 그리고 그런 경우는 \(-1\)을 출력하면 됩니다.

순환참조가 이루어지지만 물약을 만들 수 있는 경우는 어떨까요? 물약 \(A\)를 써서 \(B\)의 최소값을 업데이트 한 후 다시 \(A\) 값이 바뀔 수도 있을까요. 만약 그렇게 된다면 \(M\)번의 업데이트로 모든 정점을 방문 완료한다는 보장이 없을 수도 있습니다.

조합식 \(1: A = B + C…\)와 \(2: B = A + C…\)가 있고, 다른 조합식을 통해 \(A\)를 만들 수 있다고 합시다. 그 경우 \(B\)를 만드는 최적 가격에 조합식 \(1\)은 쓰이지 않습니다. \(B = B + C…\)가 되어 최적일 때보다 반드시 크기 때문에 순환참조로 최소값이 업데이트 될 일은 없습니다.

#include <iostream>
#include <vector>
#include <map>

typedef long long ll;
const ll INF = 1e9 + 1;

struct E { int a, x; };

int y[50];
std::vector<E> eq[50];

int N, M, cnt;
char expr[51];

std::map<std::string, int> idx;
std::map<int, ll> map;
std::string name;

int main() {
	std::cin >> N >> M;
	for (int i = 0, c; i < N; ++i) {
		std::cin >> name >> c;
		if (idx.find(name) == idx.end()) idx[name] = cnt++;
		map[idx[name]] = c;
	}
	for (int i = 0, a = -1; i < M; ++i) {
		name = "";
		std::cin >> expr;
		for (int j = 0; 1; ++j) {
			if (expr[j] == '+' || expr[j] == 0) {
				if (idx.find(name) == idx.end()) idx[name] = cnt++;
				eq[i].push_back({ a, idx[name] });
				name = "";
				if (!expr[j]) break;
			}
			else if (expr[j] == '=') {
				if (idx.find(name) == idx.end()) idx[name] = cnt++;
				y[i] = idx[name];
				name = "";
			}
			else if (expr[j] >= '0' && expr[j] <= '9') a = expr[j] - '0';
			else name += expr[j];
		}
	}
	for (int k = 0; k < M; ++k) { // 업데이트 M번
		for (int i = 0; i < M; ++i) { // 각 조합식을 최적화합니다.
			const std::vector<E>& cur = eq[i];
			ll cost = 0;
			for (const E& e : cur) {
				if (map.find(e.x) == map.end()) {
					cost = -1;
					break;
				}
				cost += e.a * map[e.x];
				if (cost >= INF) cost = INF;
			}
			if (cost < 0) continue;
			if (map.find(y[i]) == map.end()) map[y[i]] = cost;
			else map[y[i]] = std::min(map[y[i]], cost);
		}
	}
	ll ret;
	if (idx.find("LOVE") == idx.end() || map.find(idx["LOVE"]) == map.end()) ret = -1;
	else ret = map[idx["LOVE"]];
	if (ret >= INF) ret = INF;
	std::cout << ret;
}