[C/C++] 백준 #2251 물통(너비 우선 탐색)

#2251 문제는 고전적인 너비 우선 탐색인데, 노드의 개수가 정확하게 얼마인지 모르는 문제입니다.  하지만 상한은 정해져있습니다.

 

문제의 링크입니다.

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

2251번: 물통

 

이것은 옛날에 퀴즈에 자주 나오는 문제입니다.  3개의 물통을 가지고 정해진 물의 양을 만드는 방법으로 퀴즈를 풀었습니다.  그러한 것을 프로그램으로 푸는 방법입니다.

 

buckets

그림과 같이 용량이 정해져있는 3개의 물통이 있습니다.  C에는 물이 가득차있고, 이 물을 이용해서 A와 B에 물들을 가득 담는 형태로 했을 때, A 물통이 비어있는 상태에서 C의 물통이 가질 수 있는 물의 양을 구하라는 것입니다.

 

저는 너비 우선 탐색을 이용해서 계산을 했습니다.  너비 우선 탐색에서 방문 여부를 검사하는 부분은 집합을 이용했습니다.  배열을 이용해도 괜찮을 듯 합니다.  각각의 물통의 용량 최대치가 200밖에 안 되니까요.  더구나, A가 비어있는 상태만을 만드는 것이라면, 총 상태의 수는 최대 40,000이라는 상한을 가지게 됩니다.

 

제가 작성한 소스입니다.

//------------------------------------------------
//    baekjoon #2251 - Water bucket
//        - by Aubrey Choi
//        - created at 2019-11-25
//------------------------------------------------
#include <stdio.h>
#include <queue>
#include <unordered_set>

int main()
{
    int a, b, c, s; static char v[201];
    std::queue<int> q;  std::unordered_set<int> r;
    scanf("%d%d%d",&a,&b,&c);
    q.push(c); r.insert(c);
    while(!q.empty())
    {
        s = q.front(); q.pop();
        int ta=s>>16, tb=(s>>8)&255, tc=s&255;
        if(!ta) v[tc]=1;
        if(ta)
        {
            if(ta+tb<=b) s=((ta+tb)<<8)|tc;
            else s = ((ta-b+tb)<<16)|(b<<8)|tc;
            if(r.find(s)==r.end()) { q.push(s); r.insert(s); }
            s=(tb<<8)|(ta+tc);
            if(r.find(s)==r.end()) { q.push(s); r.insert(s); }
        }
        if(tb)
        {
            if(ta+tb<=a) s=((ta+tb)<<16)|tc;
            else s = (a<<16)|((tb-a+ta)<<8)|tc;
            if(r.find(s)==r.end()) { q.push(s); r.insert(s); }
            s=(ta<<16)|(tb+tc);
            if(r.find(s)==r.end()) { q.push(s); r.insert(s); }
        }
        if(tc)
        {
            if(ta+tc<=a) s=((ta+tc)<<16)|(tb<<8);
            else s = (a<<16)|(tb<<8)|(tc-a+ta);
            if(r.find(s)==r.end()) { q.push(s); r.insert(s); }
            if(tb+tc<=b) s=(ta<<16)|((tb+tc)<<8);
            else s = (ta<<16)|(b<<8)|(tc-b+tb);
            if(r.find(s)==r.end()) { q.push(s); r.insert(s); }
        }
    }
    for(int i=0;i<=c;i++) if(v[i]) printf("%d ", i); putchar('\n');
}

 

프로그램 자체는 각각의 물통마다 상태를 가지게 해서 조금 복잡합니다.  아마 A 물통이 비어있는 상태만 잡으면 조금 더 간단하게 만들 수는 있을 듯 합니다.