백준 BOJ 2251 - 물통

USACO(2)

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

2251번: 물통

dfs나 bfs를 사용해서

물통을 옮기는 모든 경우를 브루트포싱해주면 된다.

 

용량이 A고 a만큼 차있는 물통에서 (B,b) 물통으로 물을 옮기고자 할때,

1) A물통을 다 비울수 있는 경우 >> (0,a+b)

2) A물통을 다 비울수 없는 경우 >> (a+b-A, B)

 

이렇게 물을 옮길수 있는 경우의 수는 3P2 = 6이니까

6가지 모든 경우에 대해서 계산해주도록 하자.

 

중복탐색을 허용하면 시간초과를 받게 되니까

중복해서 탐색하는일이 없도록 소스코드를 작성해야 한다.

 

소스코드 펼쳐보기

#include <bits/stdc++.h>
using namespace std;

bool vis[234][234][234] = {0};
set<int> ans;
int A,B,C;

void dfs(int a, int b, int c){
	if(vis[a][b][c]) return;
	vis[a][b][c] = true;
	
	if(a == 0) ans.insert(c);
	
	// a->b
	if(a+b<=B) dfs(0,a+b,c);
	else dfs(a+b-B, B, c);
	
	// a->c
	if(a+c<=C) dfs(0,b,a+c);
	else dfs(a+c-C,b,C);
	
	// b->a
	if(b+a<=A) dfs(b+a,0,c);
	else dfs(A,b+a-A,c);
	
	// b->c
	if(b+c<=C) dfs(a,0,b+c);
	else dfs(a,b+c-C,C);
	
	// c->a
	if(c+a<=A) dfs(c+a,b,0);
	else dfs(A,b,c+a-A);
	
	// c->b
	if(c+b<=B) dfs(a,c+b,0);
	else dfs(a,B,c+b-B);
	
	return;
}

int main(){
	cin >> A >> B >> C;
	
	dfs(0,0,C);
	
	for(auto k : ans){
		cout << k << " ";
	}
	return 0;
}