백준14867 물통

작성일 | In

문제 링크

  • http://icpc.me/14867

문제 출처

  • 2017 KOI 전국 본선 고등부1

사용 알고리즘

  • BFS

시간복잡도

  • O(c + d)

풀이

(0, 0)상태에서 시작해 세 가지 연산(F, E, M)을 적절히 이용하여 (b + d)상태를 만드는 것이 이 문제의 목적입니다.

최단 횟수를 구하는 문제이므로 가장 먼저 BFS를 생각할 수 있습니다. 가능한 연산이 6가지이므로 지수 시간이 나올 것 같지만, 중복을 제거한 후 가능한 상태를 따지면 약 O(c + d)개 정도 나오게 됩니다.
원래 중복 방문 체크를 100000*100000크기의 이차원배열로 하려고 했지만, 행렬이 꽤 sparse하므로 공간의 낭비가 심합니다. 그래서 set을 이용해 체크를 합니다.
추가로, set에 모든 데이터를 다 집어넣으면 크게 느려질 수 있기 때문에 set을 100000만 개 만들어 적절히 분배해서 넣어주면 시간을 줄일 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> p;
set<int> s[100010];
p a, b;
typedef pair<p, int> pi;

inline vector<p> can(p now){
	vector<p> ret;

	//fill
	ret.push_back({a.first, now.second});
	ret.push_back({now.first, a.second});

	//empty
	ret.push_back({0, now.second});
	ret.push_back({now.first, 0});

	//move
	int tmp = a.second-now.second;
	tmp = min(tmp, now.first);
	ret.push_back({now.first-tmp, now.second+tmp});

	tmp = a.first-now.first;
	tmp = min(tmp, now.second);
	ret.push_back({now.first+tmp, now.second-tmp});

	return ret;
}


int bfs(){
	queue<pi> q;
	q.push({ {0, 0}, 0 });
	s[0].insert(0);
	while(!q.empty()){
		pi pp = q.front(); q.pop();
		int i = pp.first.first, j = pp.first.second;
		int level = pp.second;
		if(b.first==i && b.second==j){
			return level;
		}
		vector<p> arr = can(pp.first);
		for(auto nxt : arr){
			int ii = nxt.first, jj = nxt.second;
			if(s[ii].count(jj)) continue;
			s[ii].insert(jj);
			q.push({nxt, level+1});
		}

	}
	return -1;
}

int main(){
	cin >> a.first >> a.second;
	cin >> b.first >> b.second;
	cout << bfs();
}