백준 2251 물통

<링크>

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

<소스코드>

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 61 62 63

#include<stdio.h> #include<queue> #include<vector> #include<algorithm> using namespace std; int isVisited[201][201][201]; vector<int> ans; typedef struct status {     int h[3]; } status; queue<status> q; void bfs(); int cap[3]; int main() {     for (int i = 0; i < 3; ++i)         scanf("%d", &cap[i]);     bfs();     sort(ans.begin(), ans.end());     for (int i = 0; i < ans.size(); ++i)         printf("%d ", ans[i]); } void bfs() {     isVisited[0][0][cap[2]] = 1;     q.push({ 0,0,cap[2] });     while (!q.empty())     {         status cur = q.front();         q.pop();           if (cur.h[0] == 0)             ans.push_back(cur.h[2]);         for (int i = 0; i<3; ++i)             for (int j = 0; j < 3; ++j)             {                 if (cur.h[i] == 0)                     continue;                 if (i != j)                 {                     int tmp[3];                     for (int k = 0; k < 3; ++k)                         tmp[k] = cur.h[k];                     if (cap[j] - tmp[j] <= tmp[i])                     {                         tmp[i]-=cap[j] - tmp[j];                         tmp[j] = cap[j];                     }                     else                     {                         tmp[j] = tmp[j] + tmp[i];                         tmp[i] = 0;                     }                     if (!isVisited[tmp[0]][tmp[1]][tmp[2]])                     {                         isVisited[tmp[0]][tmp[1]][tmp[2]] = 1;                         q.push({ tmp[0],tmp[1],tmp[2] });                     }                 }                              }     } } Colored by Color Scripter

cs

<풀이>

1. 물을 옮길때, 두 가지 특성을 고려한다.

A는 A통의 총량이고, a는 현재 A통에 있는 물의 양

B는 B통의 총량이고 ,b는 현재 B통에 있는 물의 양이라했을때

A->B로 물을 옮긴다고하면

B-b <= a 일때 : b=B, a= a-(B-b)

B-b > a 일때 : b=b+a, a=0

이렇게 된다.

●B통에 넣을수있는 물의 양이 a보다 같거나 작을때는, B에는 물이 꽉차게되고 a는 그만큼만 줄어든다.

A B
7  5 ...//총량
5  2 ...//현재량

A->B로 물을 부으면, 5-2=3보다 5가 크므로 b=5, a= 5-(5-2) = 2가 된다.

●B통에 넣을수있는 물의 양이 a보다 클 때에는, A의 물은 0이될때까지 붓게되고, b는 a만큼 늘어난다.

A B
7 8 ...//총량
3 2 ...//현재량

A->B로 물을 부으면, 8-2 =6이 3보다 크므로, a=0, b= 2+3 = 5가 된다.

2. A, B, C가 있으면 옮길수 있는 방향은 다음과 같이 6가지이다.

A->B

A->C

B->A

B->C

C->A

C->B

각각 물을 옮겨보고 이미 A,B,C에 남은양이 또 나오면 가지를 뻗어나가지 않는다.

8,0,2가 한번 나왔는데 또 8,0,2를 볼필요는 없기 때문이다.

3차원배열로 체크했다. 각 통의 물의 총량은 200이 최대이기 때문에

[200][200][200] 배열을 만들어도 메모리가 터지지 않는다.

8,0,2가 뜨면 [8][0][2]=1 이런식으로 체크했다.

3. 다른 BFS문제들과 다르게 최단횟수 등을 구하는게아니고

A가 0일 때, C의 가능한 양을 구하는 것이기 때문에

그냥 싹다 탐색한다.

아무리 심해도 200*200*200이 걸릴 것이다.

그럼 시간도 터지지 않는다.