[BOJ] 물통 - Compy's Blog

물통 #

TimeLimit	MemoryLimit	Condition	TAG
2s	128MB	(1 <= A, B, C <= 200)	Implementation(구현), BFS(너비우선탐색)

각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 수 있는데, 이때에는 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 이 과정에서 손실되는 물은 없다고 가정한다.
이와 같은 과정을 거치다보면 세 번째 물통(용량이 C인)에 담겨있는 물의 양이 변할 수도 있다. 첫 번째 물통(용량이 A인)이 비어 있을 때, 세 번째 물통(용량이 C인)에 담겨있을 수 있는 물의 양을 모두 구해내는 프로그램을 작성하시오.

이 문제는 시간도 널널하고, 뭐 딱히 어려운 로직도 아닌 거 같아서 조건 달아서 구현했더니 풀리는 문제였습니다.

A가 0일때, C의 부피를 알아내는 과정이 그냥 조금 중복계산 줄이고, 탐색하면 될 것 같아서 BFS로 구현하여 풀이하였습니다.

정답 코드


#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

bool visited[201][201][201];
bool result[201];

typedef struct bottle {
    int a, b, c;
} bottle;

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    
    queue<bottle> q;
    
    q.push({0, 0, c});
    int pour;
    while(!q.empty()) {
        bottle bot = q.front(); q.pop();
        if(visited[bot.a][bot.b][bot.c]) continue;
        visited[bot.a][bot.b][bot.c] = true;
        
        if(bot.a == 0) {
            result[bot.c] = true;
        }
        
        // a -> b
        pour = min(bot.a, b - bot.b);
        q.push({bot.a - pour, bot.b + pour, bot.c});
        
        // a -> c
        pour = min(bot.a, c - bot.c);
        q.push({bot.a - pour, bot.b, bot.c + pour});
        
        // b -> a
        pour = min(bot.b, a - bot.a);
        q.push({bot.a + pour, bot.b - pour, bot.c});
        
        // b -> c
        pour = min(bot.b, c - bot.c);
        q.push({bot.a, bot.b - pour, bot.c + pour});
        
        // c -> a
        pour = min(bot.c, a - bot.a);
        q.push({bot.a + pour, bot.b, bot.c - pour});
        
        // c -> b
        pour = min(bot.c, b - bot.b);
        q.push({bot.a, bot.b + pour, bot.c - pour});
    }
    
    
    
    for(int i = 0; i < 201; i++){
        if(result[i]) cout << i << " ";
    }
    return 0;
}

물통#

물통 #