백준 2251 - 물통(C++)

문제 링크입니다. https://www.acmicpc.net/problem/2251

2251번: 물통

BFS 혹은 DFS를 통해 푸는 문제였습니다.

물통의 물을 옮겨 C물통의 경우를 구하는 문제입니다.

 

물통을 옮기는 경우를 생각하면 문제 풀기가 쉬워집니다.

1. A에서 B

2. A에서 C

3. B에서 A

4. B에서 C

5. C에서 A

6. C에서 B

 

이렇게 6가지입니다.

하지만 경우마다 2가지로 나눠서 생각해야합니다.

1. X물통을 Y에 옮겨도 Y물통이 전부 채워지지 않는 경우(딱 맞는 경우)

2. X물통을 Y에 옮기면 Y물통이 넘칠 경우

 

이렇게 나눠 생각하면 쉽게 풀 수 있습니다.

 

void AtoB_C(int A, int B, int C){
    if(A + B <= b){ // A -> B(1)
        if(check[0][A+B][C] == 0){
            check[0][A+B][C] = 1;
            q.push({0, A+B, C});
        }
    }
    else if(A + B > b){ // A -> B(2)
        if(check[A-(b-B)][b][C] == 0){
            check[A-(b-B)][b][C] = 1;
            q.push({A-(b-B), b, C});
        }
    }
    if(A + C <= c){ // A -> C(1)
        if(check[0][B][A+C] == 0){
            check[0][B][A+C] = 1;
            q.push({0, B, A+C});
        }
    }
    else if(A + C > c){ // A -> C(2)
        if(check[A-(c-C)][B][c] == 0){
            check[A-(c-C)][B][c] = 1;
            q.push({A-(c-C), B, c});
        }
    }
}

A에서 B, C로 옮기는 코드입니다.

나머지 코드도 이와 비슷합니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>

using namespace std;

int a, b, c;
int check[211][211][211];
int amount[211];
typedef struct water{
    int a;
    int b;
    int c;
}water;
queue<water> q;

void AtoB_C(int A, int B, int C){
    if(A + B <= b){ // A -> B(1)
        if(check[0][A+B][C] == 0){
            check[0][A+B][C] = 1;
            q.push({0, A+B, C});
        }
    }
    else if(A + B > b){ // A -> B(2)
        if(check[A-(b-B)][b][C] == 0){
            check[A-(b-B)][b][C] = 1;
            q.push({A-(b-B), b, C});
        }
    }
    if(A + C <= c){ // A -> C(1)
        if(check[0][B][A+C] == 0){
            check[0][B][A+C] = 1;
            q.push({0, B, A+C});
        }
    }
    else if(A + C > c){ // A -> C(2)
        if(check[A-(c-C)][B][c] == 0){
            check[A-(c-C)][B][c] = 1;
            q.push({A-(c-C), B, c});
        }
    }
}

void BtoA_C(int A, int B, int C){
    if(B + A <= a){ // B -> A(1)
        if(check[A+B][0][C] == 0){
            check[A+B][0][C] = 1;
            q.push({A+B, 0, C});
        }
    }
    else if(B + A > a){ // B -> A(2)
        if(check[a][B-(a-A)][C] == 0){
            check[a][B-(a-A)][C] = 1;
            q.push({a, B-(a-A), C});
        }
    }
    if(B + C <= c){ // B -> C(1)
        if(check[A][0][B+C] == 0){
            check[A][0][B+C] = 1;
            q.push({A, 0, B+C});
        }
    }
    else if(B + C > c){ // B -> C(2)
        if(check[A][B-(c-C)][c] == 0){
            check[A][B-(c-C)][c] = 1;
            q.push({A, B-(c-C), c});
        }
    }
}

void CtoA_B(int A, int B, int C){
    if(C + A <= a){ // C -> A(1)
        if(check[A+C][B][0] == 0){
            check[A+C][B][0] = 1;
            q.push({A+C, B, 0});
        }
    }
    else if(C + A > a){ // C -> A(2)
        if(check[a][B][C-(a-A)] == 0){
            check[a][B][C-(a-A)] = 1;
            q.push({a, B, C-(a-A)});
        }
    }
    if(C + B <= b){ // C -> B(1)
        if(check[A][B+C][0] == 0){
            check[A][B+C][0] = 1;
            q.push({A, B+C, 0});
        }
    }
    else if(C + B > b){ // C -> B(2)
        if(check[A][b][C-(b-B)] == 0){
            check[A][b][C-(b-B)] = 1;
            q.push({A, b, C-(b-B)});
        }
    }
}

void bfs(){
    q.push({0, 0, c});
    check[0][0][c] = 1;
    while(!q.empty()){
        int A = q.front().a;
        int B = q.front().b;
        int C = q.front().c;
        if(A == 0) amount[C] = 1;
        q.pop();
        AtoB_C(A, B, C);
        BtoA_C(A, B, C);
        CtoA_B(A, B, C);
    }
}

void solve(){
    bfs();
    for(int i = 0; i <= c; i++){
        if(amount[i] == 1) cout << i << " ";
    }
}

int main(){
    cin.tie(0);
    cout.tie(0);
    cin >> a >> b >> c;
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요