백준 14867번, 한국정보올림피아드 2017년 고등부 1번, 물통 풀이

문제

백준 14867번

풀이

$ F, E, M $ 연산을 실행하며, 물통에 $ C, D $가 담겨있도록 만드는 최솟값을 구하려면, BFS(너비 우선 탐색)를 사용하면 됩니다.

 

이미 방문한 정점인지 확인하는 것은 map을 사용하면 쉽게 처리할 수 있습니다.

$ F, E, M $ 연산 구현만 유의하면 쉽게 풀 수 있습니다.

소스코드

#include <iostream>
#include <queue>
#include <algorithm>
#include <unordered_map>

using namespace std;

typedef pair<int, int> pii;

unordered_map<int, unordered_map<int, int>> vis;

int ans = -1;
int a, b, ta, tb;
queue<pii> q;

void F(int ca, int cb) {
	if (!vis[a][cb]) {
		vis[a][cb] = vis[ca][cb] + 1;
		q.push(pii(a, cb));
	}
	
	if (!vis[ca][b]) {
		vis[ca][b] = vis[ca][cb] + 1;
		q.push(pii(ca, b));
	}
}

void M(int ca, int cb) {
	int ta = min(ca + cb, a);
	int tb = ca + cb - ta;
	if (!vis[ta][tb]) {
		vis[ta][tb] = vis[ca][cb] + 1;
		q.push(pii(ta, tb));
	}
	
	tb = min(ca + cb, b);
	ta = ca + cb - tb;
	if (!vis[ta][tb]) {
		vis[ta][tb] = vis[ca][cb] + 1;
		q.push(pii(ta, tb));
	}
}

void E(int ca, int cb) {
	if (!vis[0][cb]) {
		vis[0][cb] = vis[ca][cb] + 1;
		q.push(pii(0, cb));
	}
	
	if (!vis[ca][0]) {
		vis[ca][0] = vis[ca][cb] + 1;
		q.push(pii(ca, 0));
	}
}

int main() {
	cin >> a >> b >> ta >> tb;

	vis[0][0] = 1;
	q.push(pii(0, 0));
	
	while (!q.empty()) {
		pii c = q.front(); q.pop();
		int a = c.first, b = c.second;
		
		if (a == ta && b == tb) {
			ans = vis[a][b] - 1;
			break;
		}
		F(a, b);
		M(a, b);
		E(a, b);
	}
	
	cout << ans;
}