[백준] 2251 - 물통 (C++)

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

각각 부피가 A, B, C 리터인 세 개의 물통이 있다.

A와 B 물통은 비어 있고, C 물통은 가득 차 있다. 물통에서 물을 옮기는 경우는 두 가지가 존재한다.

1. 한 물통이 빌 때까지
2. 다른 한 물통이 가득 찰 때까지

물을 옮기는 과정에서 A 물통이 비어 있을 때, C 물통의 물의 양을 모두 구하는 문제다.

 

---

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

ex. 가능한 시간 복잡도, 알고리즘 선택

입출력 제한

• 1 ≤ A, B, C ≤ 200

 

bfs 함수를 사용한다. 이때 queue에 A, B, C 물통에 담긴 물의 양을 push 한다.

bfs 함수의 종료 조건을 만족시키기 위해 3차원 배열 visit[][][]을 선언해 queue에 push 된 값을 true로 만들고, true라면 중복으로 방문하지 않게 한다.

이후에 i to j의 경우에 맞춰 j 물통이 꽉 차는 경우와 i 물통이 텅 비는 경우로 나눠 로직을 구현한다.

 

---

코드 설계하기

위의 [문제 탐색하기]에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡고, 문제 풀이를 본격적으로 하기 전 이 문제를 풀기 위한 로드맵을 그리는 과정!

- 어떤 순서로 코드를 작성해야 할지
- 어떤 함수들을 작성해야 할지

1. A, B, C 입력받기
2. bfs 함수로 만들 수 있는 물통 3개의 물의 양을 구하기
   1. 3차원 방문 확인 배열을 만들어 방문한 경우 continue
   2. A 물통에 담긴 물이 0일 때 vector에 저장
   3. A to B, A to C, B to A, B to C, C to A, C to B마다 to 물통이 꽉 차는 경우와 from 물통이 비는 경우로 나눠 queue에 넣기
3. vector에 있는 값을 오름차순으로 출력

 

---

시도 회차 수정 사항 (Optional)

- '틀렸습니다'를 받았다면 왜 틀렸는지 고민해 보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
- 한 번에 맞히면 pass해도 됨!

pass

 

---

정답 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define pii pair<int,int>

int a,b,c;
bool visit[200][200][200];
vector<int> v;

void bfs() {
    queue<pair<int,pii>> q;
    q.push({0,{0,c}});
    while (!q.empty()) {
        pair<int,pii> cur = q.front();
        q.pop();
        int na = cur.first, nb = cur.second.first, nc = cur.second.second;

        if (visit[na][nb][nc]) continue;
        visit[na][nb][nc] = true;

        if (na==0) v.push_back(nc);

        // from A to B
        if (na + nb > b)
            q.push({na+nb-b,{b,nc}});
        else
            q.push({0,{na+nb,nc}});
        
        // from A to C
        if (na + nc > c)
            q.push({na+nc-c,{nb,c}});
        else
            q.push({0,{nb,na+nc}});
        
        // from B to A
        if (na + nb > a)
            q.push({a,{nb+na-a,nc}});
        else
            q.push({na+nb,{0,nc}});
        
        // from B to C
        if (nc + nb > c)
            q.push({na,{nb+nc-c,c}});
        else
            q.push({na,{0,nb+nc}});
        
        // from C to A
        if (na + nc > a)
            q.push({a,{nb,na+nc-a}});
        else
            q.push({na+nc,{nb,0}});
        
        // from C to B
        if (nc + nb > b)
            q.push({na,{b,nc+nb-b}});
        else
            q.push({na,{nc+nb,0}});
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> a >> b >> c;

    bfs();
    
    sort(v.begin(), v.end());
    for (auto i:v) cout << i << '\n';
}