[백준] 2251번 C/C++ 풀이 _ 물통



시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초128 MB205691066046.742%

문제

각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 수 있는데, 이 때에는 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 이 과정에서 손실되는 물은 없다고 가정한다.

이와 같은 과정을 거치다보면 세 번째 물통(용량이 C인)에 담겨있는 물의 양이 변할 수도 있다. 첫 번째 물통(용량이 A인)이 비어 있을 때, 세 번째 물통(용량이 C인)에 담겨있을 수 있는 물의 양을 모두 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 세 정수 A, B, C가 주어진다.

출력

첫째 줄에 공백으로 구분하여 답을 출력한다. 각 용량은 오름차순으로 정렬한다.

예제 입력 

8 9 10

예제 출력 

1 2 8 9 10

힌트

출처

  • 문제의 오타를 찾은 사람: kesakiyo
  • 데이터를 추가한 사람: methylene

알고리즘 분류

>> 소감

어떻게 풀어야 할 지는 감이 금방 왔지만 구현이 오래걸렸다. 
아직도 준비가 많이 필요한 것으로 보여진다. 

나는 dfs 를 이용하여 구현했는데, 다른 풀이에서는 bfs 를 사용하여 푼 것도 있다. 

>> 내 풀이 

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
 
int visited[200][200][200= { 0 };
int capacity[3];
int now_water[3= { 0 };
vector<int> answer_vec;  
int move_map[6][2= { {0,1},{0,2},{1,0},{1,2},{2,0},{2,1} };
 
// 방문한 노드 1로 표시 
void plusVisited() {
    visited[now_water[0]][now_water[1]][now_water[2]] = 1;
}
 
// 방문 여부 리턴
int isVisited() {
    if (visited[now_water[0]][now_water[1]][now_water[2]]) return 1;
    else return 0;
}
 
// 정답이면 vec에 넣는다. 
void answerPush() {
    if (now_water[0== 0 )  answer_vec.push_back(now_water[2]);
}
 
int dfs(int depth, int from, int to) {
    //cout << depth <<  " from = "  << from << "  to = " << to  << " _ " << now_water[0] << "/" << now_water[1] << "/" << now_water[2] <<  endl;
 
    // 현재 정보들 받아오기 위한 행렬 
    int sub_now_waters[3];
 
    // stack 에 있는 내용 받아오기 
    pair<intint> now_move = pair<intint>(from, to);
 
    // from 물통에서의 용량이 0 이면 그냥 종료 
    if (now_water[now_move.first] == 0return -1;
    // to 물통이 다 차있으면 그냥 종료 
    if (now_water[now_move.second] == capacity[now_move.second]) return -1;
 
    // 만약 from 물통에서의 남은 물의 용량이 to 물통에서 넣을 수 있는 물의 용량보다 크다면 
    if (now_water[now_move.first] > capacity[now_move.second] - now_water[now_move.second]) {
        now_water[now_move.first] -= capacity[now_move.second] - now_water[now_move.second];
        now_water[now_move.second] = capacity[now_move.second];
    }
    // 반대로 넣을 수 있는 물의 용량이 작다면 
    else {
        now_water[now_move.second] += now_water[now_move.first];
        now_water[now_move.first] = 0;
    }
 
    // 방문한 노드면 그냥 종료 
    if (isVisited()) { 
        return 1;
    }
 
    // 현재 상태 방문 저장 
    plusVisited();
 
    // 만약 A의 용량이 0이면 해당 C의 용량을 답에 저장 
    answerPush();
 
    // 현재 노드 상태 저장 
    for (int i = 0; i < 3; i++) {
        sub_now_waters[i] = now_water[i];
    }
 
    // 다음 이동 경로 push 
    for (int i = 0; i < 6; i++) {   
        dfs(depth + 1,  move_map[i][0], move_map[i][1]);
        // 원래 상태로 복귀 
        for (int i = 0; i < 3; i++) {
            now_water[i] = sub_now_waters[i];
        }
    } 
 
    return 0
}
 
int main() {
    for (int i = 0; i < 3; i++) {
        cin >> capacity[i]; 
    }
    // 초기 물 채워주기 
    now_water[2= capacity[2];
    // 방문한 노드에 추가
    plusVisited(); 
    // 정답에 추가 
    answerPush();
     
    // 다음 이동 경로 push 
    for (int i = 4; i < 6; i++) { 
        
        dfs(0, move_map[i][0], move_map[i][1]);
            
        // 원래 상태로 복귀 
        now_water[0= now_water[1= 0;
        now_water[2= capacity[2];
        
    } 
 
    sort(answer_vec.begin(), answer_vec.end()); 
    for (int i = 0; i < answer_vec.size(); i++)
        cout << answer_vec[i] << " ";
     
    return 0
}
cs

>> queue 를 이용한 bfs 풀이 

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<cstdio>
#include<queue>
#pragma warning(disable :4996)
using namespace std;
 
struct Data {
    int a, b, c;
};
 
//대문자 A,B,C 는 각 물통에 담을 수 있는 물의 최대용량
//소문자 a,b,c 는 현재 물통에 담아져 있는 물의 용량
//chk[a의 물의 양][b의 물의 양]
 
int A, B, C;
bool chk[202][202],ans[202];
 
void bfs()
{
    queue <Data> q;
    q.push({0,0,C});
 
    while (!q.empty())
    {
        Data now = q.front();
        q.pop();
 
        if (chk[now.a][now.b])
            continue;
 
        chk[now.a][now.b] = true;
 
        if (now.a == 0)
            ans[now.c] = true;
 
        //a->b
        if (now.a + now.b > B)
            q.push({ (now.a + now.b) - B,B,now.c });
        else
            q.push({0,now.a+now.b,now.c});
 
        //a->c
        if (now.a + now.c > C)
            q.push({ (now.a + now.b) - C,now.b,C });
        else
            q.push({0,now.b,now.a+now.c});
 
        //b->a
        if (now.b + now.a > A)
            q.push({ A,(now.b + now.a) - A,now.c });
        else
            q.push({now.b+now.a, 0, now.c});
 
        //b->c
        if (now.b + now.c > C)
            q.push({ now.a,(now.b + now.c) - C,C });
        else
            q.push({now.a, 0, now.b+now.c});
 
        //c->a
        if (now.c + now.a > A)
            q.push({ A,now.b,(now.c + now.a) - A });
        else
            q.push({now.c+now.a,now.b,0});
 
        //c->b
        if (now.c + now.b > B)
            q.push({ now.a,B,(now.c + now.b) - B });
        else
            q.push({now.a,now.c+now.b,0});
    }
}
 
void print()
{
    for (int i = 0; i <= C; i++)
    {
        if (ans[i])
            printf("%d ", i);
    }
}
 
int main(void)
{    
    scanf("%d %d %d"&A, &B, &C);
    bfs();
    print();
    return 0;
}
cs