[BOJ] 물통

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

Level : G5

유형 : dfs, bfs

---

📌 문제 탐색하기

A, B, C : 각 물통의 부피

 

물병의 물이 차는 가능한 상태는 0부터 최대 용량까지이므로 가능한 경우는 부피 + 1 이다.

따라서 시간 복잡도는 O((A+1)*(B+1)*(C+1))이다.

 

dfs를 이용해서 진행하였다.

 

📌  코드 설계하기

1. 부피 A, B, C를 입력 받는다. 

2. dfs를 호출한다.

- 방문한 물병을 체크한다. (무한루프 방지)

- 가능한 물통의 양을 result에 저장한다.

- 물이 이동할 수 있는 경우의 수 6가지에 대해 dfs를 재귀적으로 호출하고 A의 물의 양이 0이 되면 종료한다.

3. 결과를 정렬하고 중복을 제거한다.

4. 결과를 출력한다.

 

📌 정답 코드

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

int A, B, C;
set<vector<int>> visited;
vector<int> result;

void dfs(int a, int b, int c) {
    // 이미 방문한 상태라면 return
    if (visited.count({a, b, c})) return;
    
    // 현재 상태를 방문했다고 표시
    visited.insert({a, b, c});
    
    // A가 비어있을 때 C의 양을 결과에 추가
    if (a == 0) result.push_back(c);
    
    // 물을 옮기는 6가지 경우를 모두 고려
    // A -> B
    dfs(max(0, a - (B - b)), min(B, b + a), c);
    // A -> C
    dfs(max(0, a - (C - c)), b, min(C, c + a));
    // B -> A
    dfs(min(A, a + b), max(0, b - (A - a)), c);
    // B -> C
    dfs(a, max(0, b - (C - c)), min(C, c + b));
    // C -> A
    dfs(min(A, a + c), b, max(0, c - (A - a)));
    // C -> B
    dfs(a, min(B, b + c), max(0, c - (B - b)));
}

int main() {
    cin >> A >> B >> C;
    
    dfs(0, 0, C);
    
    sort(result.begin(), result.end());
    result.erase(unique(result.begin(), result.end()), result.end());
    
    for (int x : result) {
        cout << x << " ";
    }
    
    return 0;
}